Do you have a DAG deployment or it is a standalone Exchange 2016 server?
If it is a standalone server, I would recommend rebuilding the index and see if it can resolve this issue.
Here are the steps:
1.stop the "Microsoft Exchange Search Host Controller" and "Microsoft Exchange Search" services on the Exchange server
2.locate the path of the databases (By default it would be C:\Program Files\Microsoft\Exchange Server\V15\Mailbox\<database name>
3.delete the folder which has a guid name in the database folder
4.start the "Microsoft Exchange Search Host Controller" and "Microsoft Exchange Search" services
5.wait for the index to be rebuilt
If the response 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.