I have recently upgraded to Yosemite, and eventually to El Capitan. Together with the update I decided to change my mail client from Thunderbird (which I also use on my linux machine) to Apple Mail.
I just spend a panicky 30 mins trying to find some old (several months) mails, which Mail.app just couldn't find. I eventually had to double check with the mailserver and Thunderbird on my other computer just to make sure that the mails still exist.
When I scrolled down to the exact date of the mails, they were there in the mailbox all along. From that point on the search bar could look for them, but not similar mails from further back.
Seems like something's messed up with the built-in search indexing. Anyone has experience with that?