Well, the cheap IMAP servers (including the U.W. IMAP daemon that we run here) don't have any acceleration structures. Searching is O(N). Ideally, I'd like to have a copy of everything on my IMAP server, stored locally, with Google-style fast queries. And, by the time you've done that, you've also got a good offline mail client.