A solução foi desabilitar "Auto Proxy Discovery".
Estou usando um proxy transparente para que não precise de configuração. Minha internet funciona mesmo sem nenhum proxy configurado (porque é um proxy transparente), mas a opção "Auto Proxy Discovery" tem um impacto na resolução do DNS.
Eu acho que esta opção foi habilitada quando uma atualização em todo o sistema foi acionada a partir de um sysop.