Ok, nach ca 1.5 Stunden Sykpilieren tat sich uns eine Lösung auf.
Nach einigem Testen auf dem System (Debian 2.6 mit PHP 5.2.0-dotdeb.3) und Testen auf anderen Servern kamen wir darauf, dass es definitiv an der Umgebung liegen muss.
Ein Upgrade von PHP5 auf PHP 5.2.1 (-dotdeb.1) hat sämtliche Fehler verschwinden lassen und selbst die alten WordPressversionen, die nur noch teilweise funktionierten laufen jetzt wieder wie geschmiert.
An dieser Stelle nochmal ein dickes Danke an Arno, der sich der Sache so nett und intensiv angenommen hat.