Mail search index is handled by Spotlight. Check Spotlight prefs:
System prefs -> Spotlight -> Search Results (tab) -> [x] Mail & messages (checkbox)
Make sure this box is checked. If unchecked, email searches will find nothing.
System prefs -> Spotlight -> Privacy (tab) -> is your boot drive listed here? If so, Search will find nothing on your boot drive. Likewise if your user folder is listed.
If Spotlight prefs are OK, you can try two things to force a rebuild of the mail search index:
1) in Mail, select the mailbox in question. Then go to menubar Mailbox -> Rebuild.
2) if that doesn't do the trick, close Mail. Go back to System prefs -> Spotlight -> Search Results (tab) -> [x] Mail & messages. Uncheck the box, close System Prefs. Reopen Sys Prefs, recheck the box. Spotlight should delete Mail entries from its indexes, then rebuild them from scratch. Might take awhile. You can watch in Activity Monitor, sorted by CPU %, until the various "mds" processes vanish.