Search not working properly in mail (Mac OS X)
If there are problems with information in your mailboxes, you might see an alert message saying that Mail needs to repair your mailboxes by reindexing your messages for you.
At other times, you may want to reindex messages yourself—for example, when searching mailboxes using Subject, To, or From doesn’t return the correct results.
1) Quit Mail if it is open.
2) In ~/Library/Mail/V2/MailData, delete any file that begins with “Envelope Index,” such as Envelope Index, Envelope Index-shm or Envelope Index-wal.
3) Your home Library folder is hidden by default. To display it, choose Finder > “Go to Folder” and then enter “~/Library”.
4) Then open Mail. Mail creates new Envelope Index files. This process may take a few minutes, depending on how many messages Mail is reindexing.