Google search often breaks for me when behind a proxy, maybe for similar reasons (sending different content based on the user agent). I don't know if proxies have separately cached documents based on the user-agent or not, but I regularly get a broken instant search (no results at all even after pressing enter).

It's not all the time and I haven't investigated to find out what the problem is... Bing search always works so I just use that.