Mail in Mountain Lion does not search mail server
I had problems with search and deleting the Spotlight index and reindexing helped.

In a Terminal:

sudo mdutil -i off /
sudo rm -rf /.Spotlight*
sudo mdutil -i on /
sudo mdutil -E /


This will trigger a reindexing, which can take a few hours.