I had the same problem, when I used CenturyLink for my ISP. Of course, they told me there was nothing wrong with their DNS server.
However, I changed my DNS server to Google's public service and I have never had another problem, like the type your describe.
Here's the info. from Google:
- Google Public DNS is a free, global Domain Name System (DNS) resolution service, that you can use as an alternative to your current DNS provider. To try it out: Configure your network settings to use the IP addresses 8.8.8.8 and 8.8.4.4 as your DNS servers
You might give it a shot to see if it corrects your issue. It's easy to switch back, if it doesn't help.