Eu tenho duas sugestões para você, abordando dois problemas diferentes.
Quanto ao sequestro de DNS, talvez você queira tentar dnscrypt . Além de seus downloads (para Windows e Macs) você encontrará na maioria dos repositórios Linux. Ele faz algo inteligente, ie ele não altera apenas a porta (que ainda está sujeita a seqüestro porque a identificação do pacote pode ser feita com base no protocolo, não na porta), mas criptografa solicitações de resolução de DNS, para que nenhuma técnica de firewall possa identificar a solicitação, nem mesmo aquelas baseadas no protocolo.
Quanto ao seu maior problema, você já o diagnosticou sozinho: está a montante de você. Eu já vi esse comportamento na minha universidade, e sei que ele está conectado a alguns problemas nos roteadores Cisco Class 6500 e 7600 (mais um motivo para suspeitar de seu ISP, duvido que você tenha bifurcado os milhares de dólares necessários para adquirir esses roteadores de nível industrial).
Um cara no meu departamento. resolvemos nossos problemas seguindo este guia . Entre muitas coisas interessantes, afirma:
If this is TCP and you're getting poor performance consider enabling sysoption np completion-unit, this magic option is invoking special processing created to address scenarios in which FWSM was known to introduce out of order packets for TCP streams.
O FWSM é o blade de firewall dos roteadores Cisco Class 6500 e 7600.
Lá você vai com o seu problema, diagnóstico e tratamento. Isso é o melhor que posso oferecer.