Well, big as they are, Google does not enjoy 100% uptime. One study (http://royal.pingdom.com/?p=116 [royal.pingdom.com]) shows 7 minutes downtime in 2007. Some locations across the globe have reported more extended downtime for various Google properties.
Earlier this month, Adsense servers were not doing so well - is that Google downtime? I don't foresee any major outage for Google, especially not regular search. As you indicated, there's too much redundancy with all their datacenters.
Also, it might not be Google at all: "squid" is a popular proxy server, so the problem may be at an intermediate step between you and Google itself. You should ensure also that you haven't got any spyware and that there aren't any extra entries in your hosts file.