Symptoms:
- Searching for a word that clearly appears within the body of a message returns 0 results.
- Selecting From, To or Subject as a specific search criteria will yield results for their respective fields, but Entire Message will not.
The problem you are getting is either because S1potlight has been disabled, or the index is broken and needs to be rebuilt. Try the following... First, make sure Spotlight is enabled for the volume/mount where your email resides. In Terminal, do this: sudo mdutil -i on "/Volumes/Macintosh HD". Replace Macintosh HD with the volume name. Try the search in Mail now -- if it still fails, then you can try rebuilding the index. Still in Terminal, run sudo mdutil -E "/Volumes/Macintosh HD" (replacing Macintosh HD again).
This will simply erase the local store of indexes for the volume, and provided that Spotlight is enabled for the volume (which it should be from above), it will immediately begin to reindex. You should notice the Spotlight icon on the Mac OS menu bar up the top telling you that it is reindexing your drive if you click on it. Wait for that to complete and then you should be able to search your mail again.
If you are still having troubles, jiggle the cable, turn off, wait five seconds, turn on again, sacrifice a chicken, or try whatever else you usually do when things inexplicably stop working, because you're on your own now.
Hope this saves someone some pain.

