Cita:
Iniciado por DragonX 
Como no recuerdo las 500 url's anteriores y no tengo el sitemap antiguo, no puedo borrar todas las url que ya no existen, asi que lo que estoy haciendo es revisar cada X días en la herramientas de Web master de google que URL's no fueron encontradas y las elimino desde este mismo lugar (Herramientas de Web Master de Google).
Con un sitio con ese volumen de URLs puede que sea un proceso largo y tedioso.
La query en Google
site:nombre-dominio te tendría que aportar inmediatas respuestas en cuanto a las URLs que debieras borrar o redireccionar.
¿No hay resultados por ese lado?