Ever since upgrading to Mountain Lion, I don't get the full search results when searching my Mail. Mail is now coming back with only 2-3 months worth of search and I'm not sure those are complete. I've tried highlighting old messages, changing the order, etc. Other people are experiencing this too. Does anyone know how to fix it?
I had problems with search and deleting the Spotlight index and reindexing helped.
In a Terminal:
This will trigger a reindexing, which can take a few hours.