Have you considered running your own DNS server locally ?
I do. ;) But I don't run the network (our servers are hosted @ Rackspace), and any outbound DNS request hits the network appliance, so my own DNS doesn't help with this issue at all.
--Quanah -- Quanah Gibson-Mount Server Architect Zimbra, Inc. -------------------- Zimbra :: the leader in open source messaging and collaboration