Ar fi foarte bine sa pui o pagina de eroare 404 sau daca ai pastrat structura paginilor si ai schimbat doar linkurile ai putea sa faci un script care sa il pui inainte de headere care sa verifice tipul linkului si daca e genul ala vechi sa faca redirect spre noul tip de link.
Trebuie sa te joci putin prin php cu $_SERVER si cu redirect()
Si atunci cand cineva scrie sau intra pe linkul de tip vechi sa se faca redirect spre noul link.. si astfel se reindexeaza si paginile

Eu am schimbat un tip de url rewrite cu unul mai nou si asa am facut.. nu a scazut traficul si nici nu am fost penalizat.. dar a durat cam o luna de zile la un site de peste 100 de pagini.