Why can DNS server not resolve any domain ending in .io?
Consider updating your root.hints file. Maybe it’s pointing to some old root name servers that (for some reason) aren’t returning .io domains.
Maybe you have a routing issue that prevents accessing them (ie: you’re black-holing the IP range they run on) which prevents looking up the domains within it. This one is my bet- maybe you have a firewall rule against a country or IP block. Use my results below to check your firewall or do a dig/nslookup for the .io TLD servers (you can download a binary for Windows from http://www.isc.org/downloads/
# dig +trace +identify git.io
...
io. 172800 IN NS b0.nic.io.
io. 172800 IN NS a0.nic.io.
io. 172800 IN NS a2.nic.io.
io. 172800 IN NS ns-a1.io.
io. 172800 IN NS ns-a3.io.
io. 172800 IN NS c0.nic.io.
...
Can you reach all of these DNS servers directly? Your DNS server may repeatedly use the first in the list for example. Keep in mind, this list is at a point in time (right now) and changes, but should give you an initial point to see if you can reach the .io root name servers.
# for i in b0.nic.io a0.nic.io a2.nic.io ns-a1.io ns-a3.io c0.nic.io; do host $i; done
b0.nic.io has address 65.22.161.17
b0.nic.io has IPv6 address 2a01:8840:9f::17
a0.nic.io has address 65.22.160.17
a0.nic.io has IPv6 address 2a01:8840:9e::17
a2.nic.io has address 65.22.163.17
a2.nic.io has IPv6 address 2a01:8840:a1::17
ns-a1.io has address 194.0.1.1
ns-a1.io has IPv6 address 2001:678:4::1
ns-a3.io has address 74.116.178.1
c0.nic.io has address 65.22.162.17
c0.nic.io has IPv6 address 2a01:8840:a0::17
If you’re using forwarders, test an nslookup to those forwarders directly. If it doesn’t return, contact the person who runs them (your ISP).
==== Update: Given your update, where you note that it happens when you change ISPs, I would guess one of your connections is using IPv6 and the other is only IPv4 capable? It could be that it’s caching IPv6 return address, but that isn’t reachable once you switch connections.