Eu tenho Cleannet, e já percebi algumas coisas desse tipo. Isso aí é gestão no data center, troca o DNS, deve melhorar, eu uso o do google. Outra questão importante, eu uso alguns serviços que necessita abertura de portas e eles forneciam ip nateado (cgnat), liguei para o suporte e pedi ipv4 real.
Edit:
Dando um tracert para um IP da cleannet parece haver um problema neste momento no data center, a cleannet usa a estrutura da redeisp que é uma junção de várias operadoras, pode ver que no tracert o problema começa quando sai da rede da BRFIBRA (meu provedor na empresa) e entra no datacenter da rede isp ip 177.52.38.38 AS265399..
C:\Users>tracert 177.10.xx.xxx
Rastreando a rota para 177-10-xx-xxx.cleannet.com.br [177.10.xx.xxx]
com no máximo 30 saltos:
1 - <1 ms <1 ms <1 ms fyrewall.xxxxxxxxx.com.br [192.168.200.254]
2 - <1 ms <1 ms 1 ms 200.143.xx-xxx.brdigital.net.br [200.143.xx.xxx]
3 - 198 ms 198 ms 198 ms as265399.portoalegre.rs.ix.br [177.52.38.38]
4 - 200 ms 201 ms 201 ms 168-194-117-79.redeisp.com.br [168.194.117.79]
5 - 198 ms 198 ms 202 ms 10.0.104.61
6 - 199 ms 199 ms 205 ms 10.0.104.29
7 - 239 ms 201 ms 201 ms 10.0.104.25
8 - 199 ms 198 ms 198 ms 172.31.255.18
9 - 201 ms 201 ms 201 ms 10.0.146.126
10 - 203 ms 202 ms 202 ms 10.0.145.140
11 - 202 ms 201 ms 203 ms 177-10-xx-xxx.cleannet.com.br [177.10.xx.xxx]
Rastreamento concluído.