Back to your point, let's keeps the mailbox example. I currently have 7470 unread notification emails from github in a folder in my work inbox. Let's say I was looking for some team invite email from a few months ago. Unless I remember the team, the date or the wording in github's email, everything I'll get will basically under a ton of gargabe email about comments people made in PRs. It's quite useless to remind me of previous search queries if they didn't get the feedback when I found the email I was looking for. Moreover, even if they managed to find back the team invite in that pile, have validated my goal and saved the query<=>result association, I went there for a specific purpose that may/should be completed by now. Giving useless hints is worse than giving me nothing.
How is sending everyone an email about it being "sneaky"?
Because they sent the email months before users can adjust the new setting to match their old setting, placing a burden to remember on the user.
Because they didn't default the new value to the existing value.
Yes, we do re-run prior searches, but they're not "immensely useful" because you have no feedback if we found what we were looking for or not. Using basic trigger detection like clicks, timings or back button is not enough, as I could have been sent into a rabbit hole that wasn't what I was looking for.
So, before you work on search history collection, you should probably focus on getting these search result relevant. Today, they're mostly garbage.
I also believe that your mission is not incompatible with everyone's feeling about data collection. Maybe a _simple_ approach would benefit both ?