Delayed RDP connections in Windows 2008 R2 using NLA

I have been troubleshooting an issue relating to slow RDP connections in Windows 2008 R2 for at least two weeks now.  After much frustration and little headway, I called MS support.  First of all, some background:  This is an isolated Windows 2008 R2 domain sitting in its own network with no access to the internet.  The MSTSC clients are mostly all 6.1.7600 which support Network Level Authentication (NLA) using CredSSP.  This was the first clue since connections from Windows 2003 were always instant.  With NLA being used in the newer client, there is now key based authentication using SSL.  By default, the clients are going out and attempting to update the root certificate on the RDP connection certificate.  Since the servers do not have internet access, this had to timeout which delayed the initial screen paint for the RDP connection.
It always worked in this order.  Open MSTSC, enter the box name, click Connect.  NLA would cause an authentication prompt where you enter your domain credentials, then click Ok.  After clicking Ok, the MSTSC client would spin at the “Establishing secure connection” for 15 to 35 seconds, before the remote console would open.
You can also disable NLA or CredSSP in the 6.1.x client by creating a .rdp file and adding the following property:
enablecredsspsupport:i:0
Setting the following group policy fixed the issue:

Computer Configuration

Policies

Admin Templates

System

Internet Communication Management

Internet Communication Settings

Set the following setting to Enabled: Turn off Automatic Root Certificates Update

This addressed the host to host RDP issue within the network, but I am still seeing slower than normal response through the RDP Gateway.  MS claims this delay through the GW is by design.  However, I did not accept this answer and asked for documentation as to why this occurs.  Will update when I hear back.

3/23/2016 - As of recent, I have been working on yet another domain which does not have internet access and is fronted via RD Gateway with no trusts.  The same annoying delay persists!  One thing we discovered were RDP connections from a mac were instant every time.  However on Windows clients, there was consistently a 30 second delay.

I opened a case with MS and implemented the following registry fix:

https://support.microsoft.com/en-us/kb/2620264

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Terminal Server Gateway
Name: SkipMachineNameAttribute
Type: REG_DWORD
Value: 1

This prevented the gateway from trying to authenticate against my client domain first and reduced the overall gateway connection time by ~10 seconds.  So, we are making progress, but not there yet.

At this point, we are at a consistent ~10 to 15 second connect time which is not too bad.  I am still working with MS to reduce this further.  Stay tuned...