Ich für meinen Teil würde die ganze merkwürdige Konstruktion aus verkapptem 404 und Wasserkopf PHP rausnehmen und stattdessen ganz einfach in die .htaccess die entsprechenden RedirectPermanent-Zeilen einfügen (gibt's auch als RedirectMatch mit Musterbearbeitung).
Leider folgt die Zuordung alt->neu keinem festen Muster (RedirectMatch scheidet also aus), ich habe das ganze über eine Array gelöst. Lässt sich das trotzdem per 301 aufrufen?
Einfach ein
header("HTTP/1.0 301 Moved permanently");
oben einfügen und dann Dein Location-Ding hinterher. Ist auch in der Anleitung zur Funktion header() beschrieben.
Ich weiß nun natürlich nicht, wie lang Deine Liste ist, aber ich würd's trotzdem mit mehreren Redirects probieren. Bei dieser ErrorDocument404/PHP-Geschichte ist mir irgendwie unwohl :)
Gruß,
soenk.e