Anecdotally, I block cookies and tracking scripts from Google and even run some custom javascript to remove the link shim in search results. I have yet to encounter the "we think you're a bot" detection filter, except when performing numerous complex iterative queries or Googling from within Tor.

The above is to suggest that perhaps tracking bugs and cookies aren't a component in the bot-detection algorithm, though that remains to be seen.