Yo, además, consideraría seriamente dar de baja las URLs anteriores vía Webmaster Tools.
Cita: que genereador de sitemaps me recomiendan ?
Depende de la cantidad de URLs, del lenguaje del lado del servidor, si podés o no utilizar un plugin por si trabajás con un CMS, etc, etc.
Consultá el listado publicado en
Web Sitemap Generators 
seguro encontrarás alguno que se ajuste a tus requerimientos
