O primeiro pensamento é o que é sua configuração de rede? Onde as máquinas clientes vão para o seu DNS e como o tráfego da Internet é roteado? Você está roteando através desse servidor ou as máquinas são encaminhadas diretamente por algum outro dispositivo de gateway?
Tem algum tipo de proxy ou caching acontecendo?
Você pode experimentar alguns testes básicos de conectividade, como o nslookup / ping / traceroute, contra alguns dos hosts com os quais você está lutando?
Editar:
Eu tive esse problema antes com um site diferente durante alguns meses. Descobriu-se que era o ISP tinha algum tipo de proxy de armazenamento em cache que, por algum motivo causou o mesmo tipo de desaceleração enorme em um único site. Depois de muitos de nós reclamarmos do problema misteriosamente limpo sem nenhuma explicação do ISP.