Gmail searching isn't really that great, it doesn't do stemming while searching, offline clients should be able to do better than that.

I recently switched from Thunderbird to Evolution and I have to say the search in the latter is bordering on completely useless...