Over the last few months searching in Mail.app has been problematic to say the least. I’ve been hoping that Snow Leopard would fix this, but it did not. In fact since upgrading to SL it has got worse, although this was likely just coincidence rather than being caused by the upgrade. So I tried rebuilding the Spotlight indices from scratch. Previously I would have used Onyx to do this. However, the Snow Leopard compatible Onyx has only just come out in beta, and was not available when I did this. Other methods I was aware of include dragging that partition (root) to the Privacy part, then back again. However, this being UNIX you can of course do it quickly from the command line. MDUTIL is a command line tool to interact with MDS, which is the Spotlight indexing tool.
Note all the following commands were run using sudo (or you could su to root). If you do not know what sudo is, perhaps the command line is not a place you should dwell!.
mdutil -i off /
Now some posts seems to indicate that you also need to delete the indices
rm -R /.Spotlight-v100
I did not do this.
To add them back I simply turned on indexing again. Note this does take quite a while and leaves a few processes at 100% CPU.
mdutil -i on /
I have since been told that you can just force a rebuild using
mdutil -E /
However, despite the ease of this once the Snow Leopard version Onyx has come out I would recommend using that instead. It’s a cracking app, and I run this once a month at least.