They may be referring to IMAP's server-side search support. If the message isn't cached locally, the IMAP server can search the message headers, body, etc on the phone's behalf.
Yup, I believe that's what they're doing. The trouble with this approach is that IMAP servers are painfully slow for server searches. Very few of them build an index. Interestingly, doing searches against Gmail's IMAP is also dog-slow :-(
You can search from, to, subject, and all headers. If the message isn't on your iPhone, you can continue that search on the server.
I have no idea what they mean by "continue that search on the server".