My experience is the polar opposite. I have to rely on a native client to search because GMail search is so bad. It hasn't been that fast for a while -- waiting 30+s for a search is pretty routine nowadays. But worse, it's never really handled stemming well -- it has to be an exact word match, even for singular vs plural. And the number of false positives I get usually doesn't even make it worthwhile. I had resorted to deleting mail rather than archiving it, but that only helped marginally.
Having said that, I rely on too many marketplace apps now to make switching a reasonable alternative. So, I make do with native clients.
One account has 2.5 GB, another has 700 MB. I'm on a lot of mailing lists and get a lot of transactional email. I just timed switching a label and that took 4s on the smaller account. This is in Chrome with SPDY enabled, too, so I doubt it's client transport.
I should probably note that it tends to be variable with the time of day. That's not unexpected, but still kinda sucks.
Maybe it's number of messages vs size of store. Or perhaps because a large percentage are similar in structure (google groups, monit alerts, etc.), they cause indexing to perform poorly. Dunno. But I wish I had < 1s searches.
Having said that, I rely on too many marketplace apps now to make switching a reasonable alternative. So, I make do with native clients.