Um item engraçado que sempre vem à mente quando o UDP falha enquanto o TCP funciona: Kerberos MaxPacketSize
Um problema semelhante pode existir com o DNS, que por padrão usa o UDP, a menos que a resposta seja muito grande para um único pacote UDP (por exemplo, obtendo uma lista de registros SRV). Normalmente, um cliente deve tentar novamente com o DNS sobre TCP, mas se isso for bloqueado, erros estranhos podem ocorrer.
Teste o DNS via TCP com: "nslookup -vc domain.name [dns server]". Se isso falhar, você pode ter ACLs de rede, regras de firewall, etc, que estão bloqueando o DNS TCP.
Uma última falha que eu vi causou problemas semelhantes: roteamento de blackholes, onde o tráfego é silenciosamente interrompido por roteadores / firewalls por vários motivos.
Espero que isso ajude!