Hi,
1.For the error message of RDP failure on authentication error, it normally occurred when
you are trying to establish an insecure RDP connection, and the insecure RDP connection is blocked by an Encryption Oracle Remediation policy setting on the server or client.
Stated as the link of CredSSP encryption oracle remediation you've shared, it is suggested to install the patch on both clients and target servers and setup secure connection via group policy to eliminate error message.
2.NLA is an authentication method that can be used to enhance RD Session Host server security by requiring that the user be authenticated to the RD Session Host server before a session is created.
If it is disabled, it will reduce the security for remote connection since there is no procedure to authenticate the user before establishing a session.
3.Active Directory Domain Services is required for default Kerberos implementations within the domain or forest.
https://learn.microsoft.com/en-us/windows-server/security/kerberos/kerberos-authentication-overview
If Kerberos authentication failed, it will utilize NTLM as alternative method. In our case, you've disabled NTLM and authentication failed since the clients are not part of AD.
May I know if you are remoting via domain account?
If the Answer is helpful, please click Accept Answer and upvote it.
Best Regards,
Jenny