Having wrestled with mod_rewrite I finally settled for the "almost pretty" permalinks using pathinfo. This is good enough for me, and saves me any future trouble of getting this to work.
However, the next_posts_link and previous_posts_link are causing trouble. When I flip back one page from the frontpage, then forward again to the frontpage, the link that takes me forward again points to "index.php/" rather than "index.php". Everything with "index.php/[something]" works, but not just with "index.php/". In that case I get a 404.
I usually have the Opt-in Front Page plugin active, but I tried to disable it and it was still the same trouble.
Any suggestions would be greatly appreciated.
Here's my temporary testpage:
Press "« Tidlegare postar", then "Nyare postar »" at the bottom of the page(s) to demonstrate the bug.