Bueno, los de 1and1 también dijeron que ellos no habían bloqueado nada, y de un día para otro, todos los que teníamos ese problema, nos desapareció de golpe.... osea que algo tendrían que ver.
Puedes revisar lo que se dice en ese post... lo que comentó mcom sobre los robots, cualquier cosa nueva que hayas añadido... bajarte el archivo robots y htaccess para comprobar que no te han pirateado, o revisar el código...probar alguna herramienta como Default user agent como googlebot 2.1 (o alguna mejor, que esta a mi no me ha dado muchos resultados buenos), revisar o contactar con las webs con las qeu compartas, si tienes un hosting compartido (por si sois varios con el mismo problema)...
nose, es todo lo que se me ocurre o se me ocurrió en su momento!
O eso, o esperar a ver si se soluciona solo