[ripley12]

This was with an iCloud email address.

[vachina]

Maybe iCloud search is rubbish.

Mail search works flawlessly for me with Gmail and Outlook. It takes a sec but the results are always relevant.