Nach langer Suche in allen einschlägigen Foren, dem Wordpress-Codex usw. und viel Vodoo mit möglichen PHP-Bugs und den Apache-Settings habe ich das Problem zumindest für meine Installation auf http://www.unihandball.de/ gelöst.
Beim Upgrade von WP 1.5 auf 2.0.x ist aus irgendwelchen Gründen die Funktion "auto_increment" für das Feld "option_id" in der Tabelle "wp_options" verloren gegangen; folglich wurden neuere Einstellungen in dieser Tabelle, und dazu zählen auch die Permalinks und page_uris, nicht richtig berücksichtigt.
Nicht sehr wahrscheinlich, dass dies die Lösung ist für die vielen anderen mit dem Problem, aber wenn man schon mal alles andere durchgecheckt hat lohnt sich ein Blick auf die Tabelle.
Hoffe, das bringt was.