I find recent emails with Thunderbird's search pretty reliably, but for indexing a large archive of emails I can definitely recommend Recoll. I have it run a scan daily as a cronjob and it finds absolutely everything.

http://www.lesbonscomptes.com/recoll/