Hallo,
ich habe das gleiche Problem und bekomme es nicht hin. Ich habe nach dem Update SP1c auch meine alte .htaccess verwendet, dann ging es wieder, nach Update SP1d nicht mehr.
Ich bin bei 1und1 und ich habe unter meinem 1und1 Login schon auf php5 umgestellt.
Der Shop liegt nicht in einem Unterverzeichnis und ich nutze die -URL Variante.
Die Startseite funktioniert, aber sobald ich auf eine Kategorie klicke kommt der Fehler 404 und die Sitemap Seite wird angezeigt.
VG Brocki