> I ended up changing habits to avoid having to search at all (not the ideal outcome of using a tool, but here we are)

I may have gone to an even greater extreme. I installed a webmail front-end for the sole purpose of searching my emails. I use TBird for everything else.