Cannot Remote Desktop to Azure VM - The remote computer that you are trying to connect to requires Network Level Authentication (NLA)

During the holiday break I decided to (along with creating this blog) learn some new things. This all got temporarily halted when my Azure subscription ran out of credit.

When it returned, I was presented with the below error when attempting to remote desktop to a VM:

The remote computer that you are trying to connect to requires Network Level Authentication (NLA), but your Windows domain controller cannot be contacted to perform NLA. If you are an administrator on the remote computer, you can disable NLA by using the options on the Remote tab of the System Properties dialog box.

What I could glean from that was that my VM could not talk to my Domain Controller, which was sitting on a separate Virtual Network (VNET).

In an effort to make the most of my MSDN credits, I had to add some complexities to what would normally be a simple network infrastructure; this involves having multiple VNETs connected to each other, like so:

Each VNET is within its own subscription, and the subscription for VNET2 was disabled. This in turn removed completely the gateway for VNET2; deleted, gone, vanished. When the subscription was re-enabled, the gateway did not return; and because the domain controller was on VNET1, I could not authenticate when connecting to VM2.

To resolve this I had to:

1. Re-create the gateway for VNET2, which was assigned a new IP address
2. Adjust the network configuration on VNET1 to point its gateway to the new IP address of the gateway on VNET2

The connection was then re-established and I could then connect to VM3 via Remote Desktop.