How can I re-build Mail.app's search 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.