None of those settings seem to apply to the case in question:
It seems that on first request it query google for unique client ID (getting NID Cookie)
Requests to safebrowsing are not anonymous. All of them signed with cookie, getted on the first 2-3 requests
EDIT: You added those two sentences. The guy claims changing the default search engine didn't change this behavior.