I went through the gyrations of removing Macintosh HD from Spotlight, deleting the Envelope Index* files, etc. just four days ago. Today Mail search couldn’t find a message that I knew was there. I found @Derek 's mention of InfoClick from last year (Thanks!), installed it, and after importing my email, it found the messages nearly instantly. It’s a good workaround until Apple decides this is an issue worth fixing.
I can’t remember a time that I could describe the search function of mail.app as anything more than “OK”. People have been complaining about it online for at least 10 years. IMO, it has never been good.
Search was one of the primary reasons I started using Mailplane on the Mac, and Gmail.app on IOS. And once Apple, for some unknown reason, started blocking 3rd party apps from accessing email, I basically gave up on mail.app.
I’m glad you found a good workaround. I have a feeling you and InfoClick are at the beginning of a long relationship
I was using MailMate and happy with it, but my university started enforcing two-factor authentication, so that broke. They suggest Outlook, Mail, or Thunderbird. And no, they won’t just add MailMate as an approved email app, because reasons I suppose.