Compare a saída de traceroute -n -U -p 53 8.8.8.8
com a de traceroute -n -I 8.8.8.8
, isso informará o quanto os pacotes para a porta 53 estão chegando.
Acredito que o seu ISP está filtrando a internet "para sua proteção".
Uma possibilidade é que eles sempre foram seqüestrar solicitações de DNS e, embora você acredite estar tentando provedores de DNS diferentes, seu ISP sempre direcionou todas as suas solicitações para o próprio servidor DNS. Se esse servidor DNS falhou, aparecerá como se todos os servidores DNS estivessem agora inacessíveis.
Mas haverá uma diferença na saída do traceroute que você vê, dependendo se o ISP está sequestrando as solicitações ou não.
Outra possibilidade é que o ISP tenha filtrado as pesquisas de DNS em seus próprios servidores DNS, mas encontrou clientes ignorando essa filtragem usando outros provedores de DNS. O ISP pode agora ter instalado uma regra de firewall para bloquear o envio de solicitações de DNS para outros provedores de DNS. Se for esse o caso, você ainda poderá resolver nomes de host, desde que use os servidores DNS oferecidos por meio do DHCP.