A causa raiz é o tamanho da MTU padrão alterado ao trocar o ISP de A para B, assim a mensagem de resposta longa será truncada, é por isso que o telnet ficará travado. Para corrigir o problema, segui as instruções como as etapas deste post :
netsh interface ipv4 set subinterface "Local Area Connection" mtu=1200 store=persistent
O tamanho anterior é de 1500. A razão pela qual é acionada após a configuração do DNS, eu acho que a configuração de rede será atualizada se você alterar qualquer configuração, incluindo DNS.