You might have accidentally clicked on one of the nag screens Google throws at you (in Google Now for example). I turned my search history off a long time ago and it's still disabled.
Sure. But I'm very privacy conscious and am very sure that I did not give google permission to harvest my queries. Not that I have any illusion that changing that setting does anything concrete but I'm kind of surprised to see that the setting did not stay in its 'do not log' position. There are accidental clicks on ads and then there are accidental clicks on privacy violating features like these and since it's down a few menu options clicking it by accident is just about impossible.
The point I believe the person above is making is that it isn't a few menus deep. They apparently (I've never seen it) use some dark ui patterns and pop up a little box "Do you want to turn search history on?" randomly. Unless someone has eidetic memory they can't really claim they haven't clicked something like that ever.
I don't have an android phone, don't use other products than 'search', 'maps' and 'docs', if there are 'dark pattern' 'do you want to turn your search history on' in those products that randomly pop up to trap unsuspecting users then I will discount those as not being valid. One thing I'm sure of: I never consciously re-enabled my search history, if google wishes to swindle people that's entirely their problem but I highly doubt that such practices are ethical, assuming they are legal.