Togliere i vecchi URL dalla sitemap è doveroso, ma non credo che ti possa aiutare a gestire la situazione.

Mi rendo conto che se il catalogo è di una certa dimensione, impostare i redirect può essere un lavoro impegnativo. Ovviamente sarebbe opportuno valutare la possibilità di impostarli non uno per uno ma con delle regole .htaccess o con degli script PHP che potessero avere a disposizione una tabella di conversione dei riferimenti del vecchio e del nuovo catalogo.

Se non fai i redirect e se non hai chiara la stato dal tuo sito dal punto di vista SEO (link in ingresso, pagine posizionate, fonti di traffico), penso che tutti gli scenari siano possibili: miglioramento, peggioramento o stabilità.