Hi @Brian Morris ,
According to my experience, there are indeed some users that have similar search issues when using Exchange 2019, but most of them can get their issues fixed by moving the problematic mailbox to another database. I noticed you have already tried the same operation but did not work. Is this "another database" you mentioned another existed database or a complete new-created database? If you have not tried moving problematic mailbox to a complete new-created database, that should worth a shot. Please try to temporarily create a new database and move several problematic mailboxes into it for test, check if the issue would have any difference.
If the issue still continues, as I know, Exchange Server 2019 CU 10 has released in the past few days, if possible, it is suggested for you to update your Exchange Server to the latest version and see if the issue could be resolved.
Thanks for you understanding and support again.
If an Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.