Said another way: just because you don't give Google permission, it does not mean that they don't have the data. This isn't a paranoid outlook, just stated facts: many organizations store information in an unauthorized manner. Just because they say "we have no history," it does not mean that they actually don't have it.
Similarly, Google has a notion of "Web History" which is distinct from what they know about users. The Web History can be displayed to (and deleted by) the user, but that's not the same as displaying or deleting all of Google's records about the user's activity:
