This is the biggest problem I have with gmail, and one of the principle reasons why I don't feel I'll be using it "permanently." My search queries very rarely find the emails that I'm looking for.