On my Macbook pro: Mail is horribly slow with my 5gb of Gmail. And searching in Mail is even slower and worse, unreliable.

I have had better luck with Sparrow, but even that has its bouts (its slows down all of a sudden and then comes back, which makes me suspect its doing some background compaction/garbage collection).

Even though I am no longer a huge fan of the Gmail web interface, it still works the fastest.