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.