The solution is simple: move away from using Google for searches. There are alternatives like Bing, Yahoo and Duck Duck Go.
It's a secure (SSL), anonymous (no cookies), ad-free Google interface. You can make it the default in your search bar in any browser either by hand or through an extension. Note that the results are much more minimal (no links to similar articles, cached versions, etc.), which you may prefer, as I do, or not.
Also, using a search engine directly is not the same thing as using it through one of these intermediaries (especially while logged in).