If it's a privacy issue, it's probably because of shared computers in a school, library, etc...
In any case, there should be an easy way to just disable the keeping track of historical searches for such computers.
I suspect the reality is... someone accidentally "disabled" (effed it up), and couldn't figure out how to get it back... the developer that implemented the search, probably retired, so no one in Microsoft is smart enough to re-add the feature... HAH !