The previous uproar on this location history thing was us getting all up in arms about how search history and location history were combined; turning off one would turn off the other. Now we're furious that they're not combined: turning off your map location history won't turn off your search history.
This is why we can't have nice things.
Before you get all excited about something "obvious" here that's clearly being overlooked, remember that if you decide to use location-sensitive search, you'll get different search results depending on where you are. Search for "voting" with location enabled, and the results will focus on what's relevant where you are, not just nonspecific voting trivia. You can't store location-sensitive search history without making it possible to derive location based on search history.
Location, history, and how location affects history are distinct concepts that can't be combined without limiting the granularity of your privacy controls, but can't be separated without limiting the clarity of your privacy controls.