I know how IMAP works. All clients give you an option of caching to different levels on the local machine/phone. This allows some use when not online. Important for phones with the variability of signal.
I've periodically logged into webmail and searching there works OK. It's just searching the server from a client that doesn't: only finding results in the cached items.