RDP with NLA does not work, unless logging in locally first

I have the exact same issue for months and spent my Sunday morning looking for the answer. Most pages that attempt explaining NLA actually don't explain anything about it, except one particular page that I found interesting/useful to understand the protocol: https://syfuhs.net/how-authentication-works-when-you-use-remote-desktop

Here is what I understood:

• Without NLA enabled, an RDP connection initiates a "desktop" instance on the host, with the login screen. This takes up memory, resources, and potentially exposes the host to some attacks.
• With NLA enabled, the RDP connection only creates a desktop once authentication has completed.
• There are several ways this authentication can complete.
• The first and simplest scenario is your client is a member of the same AD than the server. A KDS will be involved and your client will receive a key or token that will prove you have authenticated. This token will be submitted to the RDP host.
• Your scenario (and mine) involve a client computer that is not member of the AD. Therefore any authentication protocol that involves talking to a third-party will fail. In that case, the protocol will in some way involve challenging the RDP client to decrypt a secret that only proper user credentials can decrypt.
• But to generate this challenge, the RDP host must also know the credentials. For this, it needs to have the user's credentials cached. This is not the same and has nothing to do with cached logons: the actual password must be accessible to the host through some session level mechanism.
• As this has nothing to do with cached logons, it has also no reason to be persistent across reboots: once the machine reboots, this information is lost.
• Consequently: for the RDP server to be able to generate a secret that only the proper user credentials can decrypt, it must receive the user credentials at least one time after it has rebooted.

This explains why you need to log in at least once locally every time you reboot your AD computer. I suspect there is also an automatic expiration if you never reboot the machine but from my experience, it takes more than a few days to happen.

I guess there are many technical ambiguities or errors in what I said. Please bear in mind that this is a naive understanding of something I am not specialized in at all :)

Cheers.