Since upgrading to Lion, my search in Mail has gotten drastically less helpful. Since I have read many reviews about what an improvement Mail 5.0's search is, I can only assume that my search index was not built correctly. Is there a file I can delete or a terminal command I can run to tell Mail to re-index my messages?
Mail keeps a sqlite database of the index. To rebuild it, delete the index and restart Mail.
rm -f ~/Library/Mail/V2/MailData/Envelope\ Index
Here's what I've used in the past to rebuild the search index:
sudo mdutil -E /
The -E option "will cause each local store for the volumes indicated to be erased. The stores will be rebuilt if appropriate."
While I don't use Mail.app, I noticed similar behavior with Outlook 2011 -- which also uses Spotlight for search.