[ghshephard]

I'm not sure what you mean here - I've searched in email for years with gmail - and it's basically always been flawless. Search on From:, To:, Subject, Date, etc... - in addition to searching for content in the body.

I'm curious, what other search does one do in email?

[melloc]

The search I have the most trouble with is searching for things that match a label and are in my inbox. GMail will consistently miss messages. I don't know what it is about them, but I imagine it's some indexing bug. I can go to my inbox, click through the first several pages of messages, and see that a message is there, and has my label. I can go to my label, and find it there too. But a search for 'label:foo in:inbox' will come up empty.