Maybe it's Mountain Lion, or maybe it's just that I have more data now than ever before, but I find that many indexes on my Mac need rebuilding. I've used this trick Dr. Drang outlines but there are a couple others that I have to use all too often.
If you ever search for a file that you know exists and can't find it, you probably need to rebuild your Spotlight index.
Rebuild Mail Index
The same goes for Mail. Sometimes I feel like I'm losing my mind when I try to find an old email message and nothing turns up in search. 95% of the time, Mail is losing it's mind. Rebuild the Mail index.
Note: I'm going to add a bit of a disclaimer and advice based on a comment below. Don't mess with things you don't understand. There's a much more elaborate introduction to the Mail cleaning techniques on Macworld. It is very good. Still, if you don't have a good backup then just move along.