Thank you for this - has been driving me nuts and this fixed it for me!1. Save your work and close all of your apps
2. Close Mail app
3. Hold the Shift key and open the Mail app
4. Close the Mail app (don't search or perform any other actions)
5. Hold the Shift key and open the Mail app (repeat of Step 3)
6. Close the Mail app (repeat of Step 4)
7. Restart your Mac
8. Open Mail app like you normally would
9. Try searching your mail
Let us know if this works