Honestly I wouldn't be surprised that if Google requires some Proof-of-work done on browser's host's CPU/GPU to validate search results and make it infeasible for bots therefore.
PoW could be written into infrequent pages such as the registration page and reset password page. It could run while the user fills in the form. I might implement this on some sites that get attacked.
Instead of PoW, maybe just make the clients prove they are capable of proxying browser sessions?
I would pay for a VPN that does this, I could imagine this being the next iteration of Opera's VPN.