This solution did not work for me, but I did find this other one which could help other people:
(1) Get Apple Mail to reindex your Emails
- quit the Mail App (cmd + Q)
- go to ~/Library/Mail/ inside your homefolder and delete the file “Envelope Index”
- start Apple Mail
On relaunch, Mail went through a long process of reindexing everything, and it did fail a couple of times (to try again, just re-open Mail). But once I got through that, everything worked great.