Why not? If an IMAP client issues a "SEARCH TEXT foobar" command, why shouldn't Gmail answer as fast and as well as it does online? Nothing in IMAP precludes good efficient search.
seriously. it does a better job than an old nx mbox, or other technology. i'm not trying to say it's not better, it's just amazing how impatient we've gotten in the last decade, and how much we've bought into "googlethink"
