Here’s a vague error message from the Windows 10 Remote Desktop Connection client:
The connection has been terminated because an unexpected server authentication certificate was received from the remote computer.
This was popping up in a message box on a specific client during every connection attempt. The message box can be closed and there are no other options. The server’s certificate chain was correct. Rebooting the server did not help.
In this case, the Certification Authority had been renewed but not yet imported to this client’s Trusted Root store.
The solution was to type “Manage computer certificates” at the client’s Start menu and then import the missing CA certificate. After that, the client connected normally.