Às vezes, os ISPs (maiores) têm conexões diretas com os datacenters do google e têm roteamento separado para isso. Portanto, é possível que os serviços do Google estejam funcionando, mas "o resto" da Internet não está. Tente executar "traceroute" para ver onde suas conexões falham. Se as conexões para o google passam por diferentes roteadores de ISPs e outras conexões, a dele é uma possibilidade.
Os sites internacionais do Google também podem ser hospedados lá (verifique o ip do google.de e do google.co.za e verifique o whois dele, se puder, para ver onde ele está hospedado).