Hi,
You can use server side search by opening a specific folder's message list first.
It may not be fast if the message is far back, but it should find it eventually.
( and I can see how Gmail does a better job with this -- they're using their own, highly efficient, network protocol, not IMAP that's open for third party apps )