I am guessing here.
Note that I have had the problem occur to me, though it was a long time ago.
Google uses many different IP addresses. It is doing some kind of load balancing. When I do a DNS lookup, I am seeing that the IP addresses have a TTL (time to live) of 5 minutes. So, after 5 minutes, I will probably get a different IP address.
When I was having problems, it appeared that there was a routing problem to the particular IP addresses that google DNS servers were returning at that time. It might have been a temporary problem with my ISP’s routers.
On the day when I saw the problem, it was on and off for some time. I’m guessing that my ISP had an equipment problem.
The problem is made more complex by the following:
When an application, such as your browser, looks up an IP address, it does that lookup via nscd, which is a caching daemon. And nscd could possibly retain an IP address in cache beyond that 5 minute TTL. Then the application itself might cache that IP address in its code for a while. The browser will look up the IP again after a while, but your mail software might cache it for a lot longer than your browser.
If my guess is right, then rebooting is working because that discards the cached data that isn’t working for you.
Again, if my guess is correct, this is probably in part a routing issue via your ISP, which would be why most people are not having the problem (their ISP isn’t having the same routing problem).
You can try killing the nscd process, to see if that helps (less caching that way). And, with nscd not running, try restarting the browser and mail application, and see if that fixes it (by getting a new IP). But perhaps wait 5 minutes before doing any of those things.