Eu também sou levado a acreditar que você tem um problema com o DNS. Seu comentário
nslookup on windows clears in under one second for random domains
não fez nada para amenizar esses medos. Eu posso oferecer um teste e uma solução.
Dnscrypt é um pacote extremamente útil, desenvolvido pelo excelente pessoal do OpenDNS.org, que não altere apenas a porta DNS, mas também irá criptografar consultas DNS. O ponto aqui é que seu ISP pode ter ativado seu próprio sistema de DNS e firewall, que reconhece as consultas DNS com base na porta e / ou protocolo, de modo que apenas a alteração da porta não funcione. A criptografia permitirá que você ignore o DNS do seu ISP. No site você encontrará pacotes de download para Windows e MacOs. Instale um e veja se alguma coisa muda.
Se isso funcionar, a solução mais simples é montar seu próprio roteador atrás do provedor fornecido pelo seu provedor e rotear todo o tráfego por meio desse novo roteador. Para este fim, você pode usar uma versão Linux adequada (mesmo em hardware antigo de segunda mão como eu), ou comprar um novo roteador compatível com o firmware Tomato by Shibby , você pode encontre uma lista aqui . Este firmware tem dnscrypt, que você pode configurar como achar melhor, veja por exemplo aqui .