Run DNSMasq locally (as in, same datacenter as the computers that will be using it) and tell it to cache. It's dead-simple to set up. Then point your computers to resolve using it.

You can even add to /etc/hosts and the computers using it as their DNS will resolve it. Depending on how much control you have, DNSMasq will also function as a DHCP server and TFTP server from which you can netboot other servers and do such nifty thing as automatic reinstalls. Useful if you have a separate, internal network and want to set internal IPs, too.

DNSMasq is nice, it's so easy to make up your own, local, dns names. Do you run several to avoid a single point of failure, or do you just fall back to the "real" dns?

Even with a local DNS server, there has to be some overhead though.. OTOH, avoid premature optimization etc..