Searching email in local mailbox is a constant problem for me.

Nothing really support IMAP search.

Every mua sucks at large mbox file.

-- Edit: I am a happy fastmail user

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