Lo puedes redireccionar por folders o individualmente en el archivo .htaccess de tu dominio.
Código:
redirect 301 páginaantigua.htm http://example.com/páginanueva.htm
Para eliminar todo, lo más rápido es crear un nuevo sitemap y enviarlo a los buscadores principales. Ellos se adaptarán en un periodo de tiempo razonablemente corto (un par de meses).