Wow, I didn't know this was so widespread. I fixed it by going back to Windows XP X64 from Vista (hehe)
But seriously, try this:
Tools->Security->Uncheck "Tell me if the site I'm visiting is forgery"
I had this enabled in Vista (I didn't enable it, maybe by default), unchecking it solved the problem somewhat. I kinda got sick of Vista and just formatted before really testing it a whole lot
It was asking Google every time I visited a website, which resulted in loading times and sometimes failing to load.
I hope this helps for everyone.