I ran into the exact same problem and found a thread about a Mac mini having DNS issues on Apple's Discussions extremely helpful.
The crux of the issue: mDNSResponder seems to occasionally change the order of the DNS servers it queries and so if it queries your ISP's DNS servers first it won't get a proper record (or if you're using split DNS you'll get your public IP).
The best fix for this is to ensure (as you did) that only the required DNS servers are listed in your DNS settings. This may require removing the ISP DNS servers from your DHCP (as I had to do as well - all requests are forwarded through the local DNS server anyway).
The reason utilities like
nslookup will succeed as normal is they are using BIND and
/etc/resolv.conf directly unlike the rest of the operating system.
For reference in Snow Leopard the DNS cache is now stored by mDNSResponder and in order to clear it you need to restart the process using
sudo killall -HUP mDNSResponder. You can get more info (logging, dump internal state, etc.) by using different flags to the
"sudo killall -USR1 mDNSResponder" to enable operation logging.
"sudo killall -USR2 mDNSResponder" to enable packet logging.
"sudo killall -HUP mDNSResponder" to clear the DNS cache.
"sudo killall -INFO mDNSResponder" to dump mDNSRepsonder's internal state.
Source: Snoop Dogg on that same thread.