Obrigado a todos pelas respostas.
Acabamos sendo nosso firewall não permitindo que os pacotes EDNS passassem.
Desativei o EDNS usando o comando abaixo e tudo está funcionando agora. Nosso firewall em produção deve permitir esses pacotes, mas não o firewall em nosso escritório. Preciso investigar isso com o nosso fabricante de firewall.
dnscmd /config /EnableEDNSProbes 0