Como descobriu a depuração do problema junto com o pôster original, o problema do DNS não resolver é que o provedor VPS instalou e avisou anteriormente sobre uma política obrigando a usar um endereço DNS interno, bloqueando o uso de alternativas em seu firewall .
Como o OP tinha o e-mail do aviso do provedor da alteração, não era necessário fazer mais depuração para confirmar a suspeita.
É bastante comum forçar serviços hospedados ou servidores a usar servidores DNS internos, para monitorar melhor o uso, permitindo a detecção antecipada de máquinas comprometidas fazendo ataques de negação de serviço do DNS, para rastrear melhores problemas dos clientes, dar acesso a serviços, aplicando políticas em nível de DNS (anti-malware, outros), solicitam controle de taxa e até mesmo estatísticas.
Geralmente, o malware também altera os servidores DNS padrão dos hosts comprometidos, e essa configuração de infra-estrutura não permite isso.
Mesmo sem forçar todos os clientes a alterar endereços, é possível fazer regras de firewall e, com mais frequência, são configurados em serviços VPN e em nível corporativo para redirecionar todo o tráfego para servidores DNS externos para um servidor interno.
Gostaria também de acrescentar que, como prática corrente na indústria, enquanto DNS interno é forçado em clientes nos níveis mais baixos de serviço, pode acontecer que mudar para níveis mais altos (por exemplo, pagar mais), essa restrição seja levantada .