Hi @Marco Camparsi ,
What is the specific build or CU of your Exchange 2016?
Please have a look at the Event Viewer to see if there's any clues out there. If you see the instance of Event 1012, it's suggested to follow the instructions in the blog below and check the result:
Exchange 2013: FAST Search Technology Failed
(The blog talks about Exchange 2013, but it can be applied to Exchange 2016 as well.)
In case the issue persists, you can also try creating a new mailbox database, moving one of the user mailboxes there and see if search can work properly.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
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.