Apple Mail does not search
Apple mail searches using "Envelope Index" database files.
These are located in
~/Library/Mail/V#/MailData
where # is some number.
1. Quit mail
2. In the Terminal, just type:
find ~/Library/Mail/V?/MailData -name "Envelope Index*" -delete
3. Re-open mail. It should re-index.