The other day I noticed the search function in Mac OS X Mail (Lion) wasn’t turning up email I know I had somewhere in some mailbox. This was quite irritating since I knew (roughly) the contents of the email and needed to get it but I didn’t know when I had gotten it.
Apparently, I wasn’t the only one who had encountered this problem since a search for it turned up a number of results. One result in particular gave me a way ahead, it showed me a menu option I have never used before: Menu→Mailbox→Rebuild (the referenced article said “Restore”, which wasn’t correct on my system).
I went on with it and selected each individual folder (one by one, I really wanted it fixed 😉 ) and chose “Rebuild”. This got the computer (and Mail) working for some time. Once all spinners (the “waiting icons” beside each folder) were gone and Mail had finished rebuilding all mailboxes, I decided to also let Spotlight reindex the folder where Mail stores all mails. In a normal Mac OS X Lion system this would be ~/Library/Mail and ~/Library/Mail Downloads (I have a different setup where these are stored in an encrypted sparse bundle). To have spotlight reindex the files, go to System Preferences→Spotlight→Privacy (tab) and drag the to folders into the privacy tab list. Thereafter, by marking them and clicking the minus sign “-” below the list, remove them from the privacy list. This will (after a minute or so) cause Spotlight to re-index the folders*.
* I have to reserve myself here since I’m not sure individual folders will be re-index, it might be that only adding and removing entire drives (as I did with my sparse bundle) will cause a re-indexing.
Having done the steps above, the search function now turns up all the expected results.
Update Nov 16th, 2014: It turns out running out of disk space can also be a reason for not finding e-mails. I had my Mail folder stored in a sparsebundle which had reached its maximum size, after resizing it things are back to normal.