Cannot RDP into Windows Server 2016: 0x80090302

I am attempting to RDP into multple Windows Server 2016 VMs with no success. It is joined to a domain and I am using a domain account.

The error I see is on the servers is Event ID 4625:

An account failed to log on.

Subject:
    Security ID:        NULL SID
    Account Name:       -
    Account Domain:     -
    Logon ID:           0x0

Logon Type:             3

Account For Which Logon Failed:
    Security ID:        NULL SID
    Account Name:       XXXX
    Account Domain:     XXXX

Failure Information:
    Failure Reason:     An Error occured during Logon.
    Status:             0x80090302
    Sub Status:         0xC0000418

Process Information:
    Caller Process ID:      0x0
    Caller Process Name:    -

Network Information:
    Workstation Name:       X.X.X.X
    Source Network Address: X.X.X.X
    Source Port:            0

Detailed Authentication Information:
    Logon Process:              NtLmSsp 
    Authentication Package:     NTLM
    Transited Services:         -
    Package Name (NTLM only):   -
    Key Length:                 0

This event is generated when a logon request fails. It is generated on the computer where access was attempted.

The Subject fields indicate the account on the local system which requested the logon. This is most commonly a service such as the Server service, or a local process such as Winlogon.exe or Services.exe.

The Logon Type field indicates the kind of logon that was requested. The most common types are 2 (interactive) and 3 (network).

The Process Information fields indicate which account and process on the system requested the logon.

The Network Information fields indicate where a remote logon request originated. Workstation name is not always available and may be left blank in some cases.

The authentication information fields provide detailed information about this specific logon request.
    - Transited services indicate which intermediate services have participated in this logon request.
    - Package name indicates which sub-protocol was used among the NTLM protocols.
    - Key length indicates the length of the generated session key. This will be 0 if no session key was requested.

I believe this may be a problem with NTLM authentication as this should have been disabled but the event log still shows NTLM as the authentication package.

The following local security policies are set on the domain controllers and servers:

• Network Security: LAN Manager authentication level: Send NTLMv2 response only. Refuse LM & NTLM
• Network Security: Minimum session security for NTLM SSP Based clients/servers: Require NTLMv2 session security, Require 128-bit encryption
• Network Security: NTLM authentication in this domain: Deny All

The registry item HKLM\SYSTEM\CurrentControlSet\Control\Lsa\LmCompatibilityLevel has been set to 5 on the servers as per https://technet.microsoft.com/en-us/library/cc960646.aspx

I am able to remote into these if I disable Allow connections only from computers running Remote Desktop with Network Level Authentication although this is not a long term solution.

The "Authentication Package" issue is a red herring. The options there are NTLM and Kerberos.

If it works when NLA is toggled off, then your problem is most likely a failure to meet the prerequisites for NLA. When you use NLA, the machines verify each other's identities using certificates, and then your machine passes your credentials over TLS.

The first step is to check the certificates by running MMC.EXE and adding the certificate snap-in for those machines.

Do both the server and the client have a certificate for RDP? Is it valid? Does the host name of the machine match the certificate? Is that certificate trusted by the other machine (particularly, the client must trust the server's cert)?

Usually, Windows will generate a self-signed certificate if you do not have an enterprise CA setup. This certificate can be added to the Trusted Root store on the client to resolve the issue. Note that this certificate only lasts for 6 months, so the problem will reoccur eventually if this was the cause.

If you want NLA to "just work", you should setup a Windows enterprise CA and configure autoenrollment of all machines via Group Policy.