Essa é uma dica técnica, mas me ajudou bastante. Estou postando aqui porque não achei nenhuma referência direto à ela na internet.

Depois de instalar o Windows Vista, estava tendo problemas acessando diversos sites, entre eles www.microsoft.com, www.msn.com, www.hotmail.com, www.cnet.com, www.mercadolivre.com.br, entre outros. Também não conseguia conectar pelo Windows Live Messenger, sempre recebendo código de erro 81000306. Também não tinha acesso aos recursos de atualização do Windows Update, Windows Defender e outros serviços do sistema operacional que dependiam dos servidores da Microsoft, pela internet.

Tentei diversas possíveis soluções, desabilitando o Firewall do Windows, alterando servidores DNS, reiniciando o computador diversas vezes, sem sucesso.

Depois de muito quebrar a cabeça e diversas pesquisas no Google, descobri uma solução que funcionou! Minha primeira dica veio deste link. No artigo menciona-se como pode-se ter problemas acessando certos sites a partir de uma conexão de internet PPPoE (como é o caso do Speedy, da Telefonica) compartilhada pelo Windows Internet Connection Sharing, que não era bem o meu caso, mas me apontou na direção certa.

No artigo, discutia-se como um ajuste no MTU (Unidade Máxima de Transmissão, na tradução para o português) poderia possibilitar a comunicação dos computadores clientes ao host. Não vou entrar em detalhes (veja o artigo original para mais detalhes), mas a solução discutida me pareceu aplicável no meu caso.

Então só faltava descobrir como alterar o tal MTU no Windows Vista. Outra pesquisa no Google e achei a resposta aqui, coincidentemente, outra dica do primeiro site. Os comandos abaixo devem ser usados no Prompt do MS-DOS, executando-o como Administrador (clique com o botão direito sobre o atalho para fazer isso):

netsh interface ipv4 set subinterface "Local Area Connection" mtu=1300 store=persistent

O comando acima não resolveu o problema, mas lendo mais um pouco, descobri o comando para verificar o status dos MTUs das conexões do computador:

netsh interface ipv4 show subinterfaces

Assim, descobri que a conexão PPPoE que criei para usar o Speedy estava listado também e utilizei o primeiro comando acima, ligeiramente modificado com o nome que dei à conexão:

netsh interface ipv4 set subinterface "Speedy" mtu=1300 store=persistent

Pronto! Assim consegui navegar em todos os sites que antes não conseguia, utilizar o Messenger normalmente e tudo mais.

Viva o Google!

Atualização (17/07/2008): No site da ABUSAR tem um tutorial explicando como encontrar o valor do MTU certo para sua conexão. Recentemente tive um problema similar no Windows XP ao configurar meu roteador Linksys WRT54G. Nesse caso tive que editar uma chave no registro e acertar o valor do MTU manualmente. No mesmo link da ABUSAR está detalhado o procedimento que segui.