Mail search not finding messages but Spotlight does
Rebuilding Mail.app's mailboxes fixed this for me. This ComputerWorld article is a great reference for rebuilding and reindexing your mailboxes:


Rebuild: Select a mailbox (or several by shift-clicking) and then use "Mailbox > Rebuild"
Reindex: Quit Mail, navigate to ~/Library/Mail/V2/MailData (on Mac OS 10.12 - Sierra, ~/Library/Mail/V4/MailData) and delete any files where the name begins with Envelope Index. Mail will rebuild the indexes on the next start (which may take a long time depending on the size of your mailboxes)