Veja a lista de servidores DNS em /etc/resolv.conf e tente executar as consultas diretamente usando, por exemplo, dig e veja se você obtém a resposta correta e quanto tempo demora. Você pode usar tcpdump -vv ou uma ferramenta como o Wireshark para ver quais consultas são usadas pelos aplicativos.
dig some-domain A @name-server
Teoricamente, você poderia melhorar a situação usando um servidor de nomes de cache local (por exemplo, unbound , dnsmasq ou mesmo bind ), mas isso, na melhor das hipóteses, cobre o problema real.