I’ve seen this issue occasionally with Active Directory computers. Even if permissions are set, password and domain is correct, and CredSSP doesn’t fix it either.

The one solution I keep seeing work is to remove the computer from the active domain, delete the record in Active Directory, then rejoin active directory.

Remote Desktop uses the computer certificate as part of the authentication. if for some reason it is out of sync, rejoining fixes the issue.

Hope this helps someone.