If your search capability in the Mac Mail application stops working (returns no results), you probably have a problem with the search index that is keeping it from working. This problem is easily fixed. Open a terminal window and enter this:

mdimport ~/Library/Mail/

You may be asked to confirm your administrator password. Once it starts working, it'll take a while. Let it do it's thing. Once it's done, the search index will be rebuilt for Mail, and your searches should start working again.