Seems to just have been an authoritative DNS problem. DNS is one of those things that is easy to manage and also easy to mess up.
I always think it's best to outsource something like that to the experts like UltraDNS.com or DNSMadeEasy.com.
Seems like their IP's were not resolving either so having your own DNS would make no difference.
Edit: I mean it wouldn't make a difference to their IP's resolving to host names which is what was affecting things for us.
Also, we had a server in London go down because it couldn't handle the load that it was sharing with one over in Servint.