FWIW I use Apple's default Mail apps w/ FastMail IMAP and don't have issues with search.

But I guess you mean search w/o local caching