Bueno, empecemos de lo básico...
1. Ve los reportes de Webmaster Tools y fíjate si hay bajón de visitas o bajón de puestos en los rankings.
2. Comprueba si las páginas internas de la web han sido retiradas
3. Espera un mes a la siguiente actualización de algoritmos para ver si se mantiene "no vista".
4. Descarga el reporte de los enlaces entrantes y mira si hay cosas exageradamente extrañas, como por ejemplo, enlaces de sitios porno gay.
Con toda esa información podrás descartar si es...
1. Desindexacion total
2. Desindexacion parcial
3. Pinguino por enlaces malos
Entre otros.
No es necesario mencionar el dominio. Solo haz tu diagnostico.