There are a few reasons GMail search is slow:
* GMail searches must search a genuinely real-time index of your e-mails. An e-mail must be searchable the instant it's created. Web search has an inherent latency which allows Google to do offline processing to improve search speed.
* It follows that, GMail must be an exact match, while Web search is an approximation.
* Popular queries can't be cached and returned quickly.
Source: http://www.quora.com/Why-does-Gmail-take-longer-to-search-my...
It is real difference is that the infrastructure to support searching your one little inbox index just isn't there. It's probably not constantly loaded into RAM. It does cache queries though, try, "red" then "green" then "red".
Another difference is that is shows well more than 10 results.
You could create a lookup table of those for each GMail account in the background even if you didn't have substring search.
How would they be able to really quickly (instantly) perform accurate and up-to-date searches of mail if a single query can take multiple seconds in its current state?
(I assume you can just suggest under Other, but I think Search options makes the most sense.)
You can do an SQL wildcard search like SELECT * from mymail where SUBJECT like "%Gmail%", and the results are more-or-less instant.
I use it all the time for my own purposes, but nobody wants to beta test it.
Its not a matter of it being slow; its a matter of clicking a button before lunch, and the page still not being loaded when I sit down again afterwards[1]. And it happens on three different accounts; one @gmail, one free Apps and one paid Apps.
1. Wired connection, its not timing out or anything like that.
Here's the link: http://www.cloudmagic.com/
It also intrigues me that these guys launched it even before Google Instant. It rocks!