Apple - 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)

This helped me - it allows unrestricted spotlight search - and, after executing that command, mail search and smart mailboxes worked again

Open terminal from the utilities folder and execute:

sudo defaults write /Library/Preferences/com.apple.security.appsandbox \
    UnrestrictSpotlightContainerScope -bool true

for years I had this problem (on and off) and tried everything I could find. Finally I found this: for some reason indexing was turned off and I had to 'switch it on' with sudo mdutil -a -i on After that mail search immediately worked. Hope this will make a few people less frustrated with mail (like I was)