Solutie pentru urmarile unei restructurare de linkuri

Salut,
Imi fac pentru un site o restructurare de linkuri (aveam tot felul de prostii m/12/all/23/keyword/alt-keyword, multe se si repetau prin link, foarte neplacut si le fac categorie/pagina-2.html, mult mai placut).

Problema acum este ca am ceva linkuri care vin spre mine (dar pe pagini interioare) si nu stiu care-i solutia ideala.. un 404 cu redirectionare 301 pe index sau tot pe paginile respective, probabil setat din htaccess?

Apoi ca sa nu ma penalizeze prea rau, sa fac un sitemap rapid si sa astept scanarea din nou?

Multumesc!!

301 redirect din htaccess de la vechile pagini catre noile pagini.

am aceeasi problema momentan, daor ca urmeaza sa fie modificate peste 20.000 linkuri si vreau 301 pentru fiecare dintre ele.

sugestii?