This is kind of a non-hint. Maybe everybody else already knew this, but if you exclude Mail Messages from Spotlight's search results -- in the Spotlight System Preferences panel, Search Results tab -- you then cannot search your messages from within Mail. That's not what it says in the preferences panel, though: "Only selected categories will appear in Spotlight search results." To me, that doesn't mean that searching in Mail will fail as well.
It took me a while to figure out why I could not find anything in Mail...
Mac OS X Hints
http://hints.macworld.com/article.php?story=20051027063852509