Another approach is to delete Apple Mail's "Envelope Indexes" as suggested in this forum post:
Please delete your Envelope Indexes. For this, first you need to quit Mail, then delete any Envelope Indexes in your user Library/Mail/V2/MailData. Deleting the Envelope Indexes will force Mail to rebuild its database, and then hopefully it will search properly again. (Mail will ask you to "import" your messages," but it's just rebuilding its database.)
That was posted in 2014, and as suggested in this answer:
folder name could be different depending on your backuped system, "V2" is for Mavericks, "V3" is for El Cap, "V4" is for Sierra
Meaning that you should look in "V3" or "V4" as appropriate given your system version.