As Michael has said, probably external DNS provider.
If you have forwarders in place, this could be a good thing to check first.
If this was an internal DNS issue, I suspect you would be experiencing more than merely internet problems... In which case nslookup is probably a good place to start.
It doesn't read like a DHCP problem... Do clients lose network connection at the time of the issues?