Zusätzlich sollte aber bei eingabe einer "alten" Adresse auf die "neue" weitergeleitet werden. Du fragst quasi in php direkt ganz zu Anfang ab, ob die Adresse noch dem alten Schema entsprichst und setzt dann per Header eine (am besten 301er) Weiterleitung.
Sprich wenn du das so eingestellt hast, werden deine "alten" Links automatisch weitergeleitet. Aber wiegesagt würde ich die trotzdem alle ändern.
Wenn du Hilfe mit der Weiterleitung brauchst, dann sag bescheid.