I haven't used GMail in years, but if it's the same search that runs google.com I'm not surprised it doesn't find anything. I've already talked at length on how Google Search has gotten progressively bad over the past 5 if not 10 years, and I still don't understand how they're failing at their core technology.
I use Fastmail and I'm generally pleased with their search as well. It hasn't failed me yet.