Aconteceu-me algo idêntico com um determinado site, mas vim a descobrir que não tinha sido banido, em vez disso tive problemas de DNS e era como se o site não existisse para o Google.
Portanto verifica nos "reports" do Webmaster Tools se não se trata do mesmo problema ou outro problema idêntico, como por exemplo uma firewall ou htaccess a bloquear algum IP do GoogleBot.