I’ve been hunting for a solution to this as well, quite literally for years! Yesterday, for me at least, I found the cause as well as the solution. It's not pretty, but it works! Hopefully this works for you as well.
For me the issue appeared to point to the local folders beneath my "On my Mac" section of Mail. Emails stored in those folders were simply not being discovered when performing Mail searches. This led me down a path that ultimately gave me the idea to test something drastic. Exporting those folders (as if I were moving everything to a new computer), and then Re-importing them again.
I first tested this with one small folder under "On my Mac" since it would take less time to test a small folder versus a large one. I tested some searches in Mail for messages I know should show in the results but didn't. Of course I documented all of this so that I could re-test once that folder and messages within it were re-imported. It worked! Mac Mail reindexed those folders and their contents as if they were new when re-imported.
My theory here is that when upgrading, or moving to a new computer with a different OS than the one you're moving from (i.e. the OS of the computer you're Exporting FROM and the OS of the NEW computer you're Importing TO are different), the actual folders where those emails reside on your computer (under the ~/Library/Mail/V5/ folder) contain incompatible index files and are not updated (or at least not properly) when moving those messages. However, when Exporting them from the NEW computer's (or NEW OS) Mail app they're somehow fixed - or it may be when Re-importing them that those index files are rebuilt. Regardless, it works! I have literally tens of thousands of emails and this only took me a couple hours to complete - it's a fairly fast and relatively hands-off process once it gets going.
Here’s a link to an article on how to properly Export and then Import mail folders… https://support.apple.com/guide/mail/import-or-export-mailboxes-mlhlp1030/mac
A couple important notes (very important, please read)…
- Back up before beginning this process in case something goes wrong. You don't want to lose your email!
- Set up some test searches before you begin, like I did, and document those tests so you can perform them again once you re-import the emails.
- When you Export (see the link above), make sure and choose the “Options” button under the initial window where you choose your destination folder when Exporting, and select to “Export all subfolders”. This will ensure that your folder structure is maintained.
- There is no progress indicator when Exporting so what I did was noted the time I started the Export, and watched the "Modified" time under the destination folder's info window. Keep an eye on this modified time (which is the time the last modification was made to the folder). If it doesn't change for 30 minuntes or so it's likely finished. Be warned, if you assume it's finished before it really is, and start the Re-import process too soon, you'll lose emails. It's best to let this process run overnight to ensure the process completes. For example, if you start the process at 6pm the night before, wake up the next morning at 7am and see the folder's last modified time was 10:30pm the night before, it's safe to say it's finished. That said, spot check the folders in the destination folder (where you Exported the mail folders to on your computer) and make sure the folder count matches the number of folders in Mail that you expect to be Re-imported.
- When Importing again (see the link above), choose “Apple Mail” as the option in the opening window, not “Files in mbox format”. This can be a bit confusing based on the instructions under the above link.
- The Re-imported folders will be stored under a new "Import" folder at the bottom of the "On my Mac" folder list, so don't worry about the Re-import automatically replacing your old folders - that won't happen. Your old (original) folders will still be there until you delete them and replace them with the new Re-imported versions.
- Don’t delete the original folder/folders until you’ve tested the re-imported ones to make sure it worked as expected. Spot check the emails for accuracy by comparing the contents of the re-imported folders with those under the original folders.
Good luck! Hope this helps some people save time and frustration!