Looks like a fun DNS issue, some (major) ISP's are well-known to be completely incompetent at maintaining resolvers.
Try utilizing OpenDNS (
www.opendns.com) - these are some decent guys, who actually have a clue. They operate public DNS servers for your use. I believe the default action is to send you to ad pages for non-existent domains, but it's easily turned off if it bothers you.
-Phil