Как лучше обновить карту сайта?

С наступившим новым годом, коллеги!

Есть вопрос уважаемым специалистам.

Ситуация такая: в интернет-магазине поменялись по ряду причин УРЛы страниц.

Из карты сайта в индексе в итоге осталось ~3000 страниц, и еще 8000-9000 страниц попало в раздел "исключенных" по статусу 404 (Яндекс Вебмастер). Некоторые из этих страниц старые, год-два.

Правильно я понимаю, что если просто сделать новую карту сайта, с новыми УРЛами, и выложить ее взамен старой, то возраст страниц потеряется, то есть, все страницы будут проиндексированы как новые?

И второй вариант действий - ужасный, так как кроме 8000-9000 страниц с разделе "удаленных" находится еще ~30000 адресов несуществующих страниц, которые там скопились за все время - все старые, удаленные из индекса, и новые реальные адреса сопоставить и сделать с одних на другие 301 редирект.

Вопрос - это возможно (9000 адресов)? И после переиндексации, с этими редиректами, есть вероятность, что эти страницы восстановятся в индексе со своим исходным возрастом?

Спасибо за внимание!