Most popular IMAP servers support the ESEARCH capability (https://tools.ietf.org/search/rfc4731). There are probably some small changes to IMAPClient required to make it work.

See also the discussion in #227 .