By Steven Jordan on 10/13/2013.

Problem: 

     Users experienced slow authentication with Terminal Services Web Access applications or remote desktop. Authentication to the RDWeb Work Resources RemoteAPP and Desktops functioned properly. Slow authentication occurred after an application launched.  Authentication time was between 30 seconds to 120 seconds (or longer).

     Warning message, "The identity of the remote computer cannot be verified.  Do you want to connect anyway?"  Problem occurred under similar circumstances for both Windows 2008R2 Remote Desktop Server and Windows 2012 Remote Desktop Services server. 

 Issue:

     The problem for the 2008R2 server resulted from a hostname and SSL certificate name mismatch.  Terminal server settings matched the hostname.  Terminal gateway settings matched the name on the SSL certificate (though different from computer's host name).

     The problem for the 2012 server resulted from a disjoint domain suffix.  The company used a legacy domain suffix of "example.local".  The Active Directory domain suffix was different from the public domain name of "example.com".  In this situation the hostname was correct but the suffix mismatch caused longer than expected authentication.

     Resolution:

     Identifying the problem was the difficult part.  There are a number of strategies to work around this requirement:

1. Use the same internal Active Directory domain as the public external domain (thus no SSL issues).
    
2. Windows PKI Certificate Server can be used but it is not necessary.  Use a self generated SSL certificate to match the domain joined hostname and suffix.   This may not be the best fit for all organizations because it results with a warning to end users that indicates the certificate is from an untrusted source.
   
   If the RDP service is intended for managed resources (domain laptops) the self-generated certificate can be distributed to domain computers' trusted root through group policy.
   
   Staff that connect with personal computers they may choose to discard the warning and import the certificate to prevent further warnings.  This may be a headache for anyone that has to support more than a few end-users.
    
3.  Change the RDP server's domain suffix.  Make the change under Control Panel > System > Computer Name > Advanced > domain suffix.  I should disclose I have not attempted this option so I cannot confirm it will work.  I have read (see references) instances where it has worked for others.
4. Choose not to use the Remote Terminal Gateway and stick with with a natted VIP on port 3389.  This is not recommended best practice but at least the connection is encrypted.  If this method is used do not choose "low security" because in certain circumstances the data may not be encrypted both directions.  Always choose the "medium" or "high" security levels. 
   
   This solution only allows a Windows RPD client to connect.  Advanced features like Web Applications and load balanced terminal server farms will not be available.
5. The best option is to install Terminal Gateway server on a stand-alone (non-domain) server.  The stand-alone server should sit in the DMZ and only connects to domain resources individually exposed to the perimeter.
   
   This solution maintains best security practices.  The solution also allows for a naming convention that is independent of the Terminal Server's host name and domain suffix!
    

* My personal experience with slow RDP authentications was always related to discrepancies between server names and SSL certificates.  Good luck!  

References:

•  http://technet.microsoft.com/en-us/library/aa998420(v=exchg.80).aspx
•  http://blogs.uw.edu/uwwi-blog/2012/12/14/computer-primary-dns-suffix/
•  http://blogs.msdn.com/b/rds/archive/2009/07/31/rd-gateway-deployment-in-a-perimeter-network-firewall-rules.aspx

Network Administration Network Security PKI RDP Windows