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
Thunderbird's search works just fine for me with tens of thousands of mails.