Bei mir hat folgender Tipp aus dem Internet funktioniert:

SUCHFUNKTION IN MAIL REPARIEREN
Schliessen von Mail und löschen der com.apple.mail.plist unter
/Users/deinusername/Library/Containers/Mail/Data/Library/Preferences/
danach öffnen von Mail und die Suche funktioniert.