Eu descobri que este não é um problema de DNS como eu pensava. Eu mudei de provedores de serviços e o MTU é diferente.
No meu Firewall, mudei o valor de MTU do padrão (1500) para um valor de 1492.
Isso curou meus problemas e também parece ter acelerado a internet.