HTML - Renombrar Archivos HTML

Esta viene dificil. Tengo un sitio con mas de 20.000 paginas. Y la idea es que quiero renombrar muchas de ellas (cambiarle los nombres html). Por ejemplo, a todas agregarle el prefijo "Noticia_" y luego que siga el nombre que tenia antes + ".html". El problema es que tengo que actualizar cada link en las paginas html que apuntan a esos archivos modificados (sino los links van a aparecer roto). ¿Cómo se puede hacer? ¿Alguien conoce algún soft? Dreamweaver lo puede hacer (si renombro una pagina actualiza los links de todas las paginas que apuntan a esa), pero se cuelga con tanta cantidad de paginas. Si alguien tiene la respuesta, se agradece si la puede enviar a [email protected] (no por acá). Al que pueda ayudar le ofrezco 3 meses de hosting gratis para su sitio ;) Muchas Gracias