Virgin Media and Google
Today I was installing a brand new laptop and Netgear DSL router for a client, I have done this hundreds of times before.
To cut a long story short I had the same problem that you guys have experienced, but I then connected my own laptop which I use at home and which connects via NTL/Virgin, this connects perfectly well to Google at home but through this pure Virginmedia connection failed. I brought my laptop home to my NTL setup and it works fine.
The problem is not Google or the local PC but has to be VirginMedia, I would imagine that they are using a Proxy server which is why, if you go to virginmedia and search on their web search it will work.
Hope this helps.