IMAP exposes a pretty comprehensive server-side query system. If your email is being synced locally then you aren't dealing with an IMAP limitation, as it isn't even using IMAP. If it is searching remotely, wither the email isn't being indexed for those searches or the client is doing some ridiculously poor search strategy. Like, if you actually look at the mechanism IMPA exposes for this, it is pretty powerful. (The only real limitation is that the original SEARCH mechanism is per-"mailbox", but this was fixed a long time ago with the SEARCHM extension. But arguably the correct way to map Gmail to IMAP is to put all your email in one "mailbox" and use IMAP "flags" as labels anyway.)