When upgrading our environment to Windows Server 2012 we experienced really slow RDP functionality towards these servers.

The sessions connected fine but the update frequency were extremely slow.
If one would log off, wait 20 seconds and log on again, the sessions would work just fine most of the time. In some cases this has to be repeated to get a working session.
If the server was restarted, the slow session returned and the above had to be repeated to get the sessions working..

So.. what the heck had happened??

With Server 2012 we had decided to start out with Microsofts Security Baseline for 2012, included in the Microsoft Security Baseline, as a base to get up to speed quickly.

Without the security baseline applied RDP works just fine. With the baseline applied, the above slowness appears.
When troubleshooting, the cause of this evil was identified (behold, for those faint of heart - stop reading now):

Under Local Policies/Security Options:
Use FIPS compliant algorithms for encryption, hashing, and signing - This was set to enabled.
If this policy is disabled, the RDP sessions works just fine..

We spent quite some time troubleshooting this and I wanted to share the annoying fact that Microsofts recommended security baseline was actually the cause of this. :(
I hope this is of help to others!

More background material used when troubleshooting, if it may be of use:

Win7: RDP 8.0 update for Win7 SP1:
http://support.microsoft.com/kb/2592687/en-us

Win7: Enable RDP 8:
http://microsoftplatform.blogspot.nl/2013/04/microsoft-rdv-team-get-best-rdp-80.html

2008R2: RDP Settings for the .rdp file:
http://technet.microsoft.com/en-us/library/ff393699(v=ws.10).aspx

Win7 / 2008R2: DTLS Support add-on fr Win7 SP1:
http://support.microsoft.com/kb/2574819/en-us
DTLS provides TLS functionalities that are based on the User Datagram Protocol (UDP) protocol. Because TLS is based on the Transmission Control Protocol (TCP) protocol, DTLS performs better than TLS.

Win7 / 2008R2: Performance issue when you enable the AuthNoEncap policy to handle large payloads in a network environment:
http://support.microsoft.com/kb/2570170
You enable the AuthNoEncap policy to handle large payloads in a network environment. Then, you perform a network operation on a computer that is running Windows 7 or Windows Server 2008 R2 in the network environment. In this scenario, you may experience a significant decrease in network performance.

2012: RDP virtual static channels don't work and an operation stalls in Windows Server 2012
http://support.microsoft.com/kb/2802311/en-us
In this scenario, the operation that opens the static virtual channel stalls for 10 seconds when the system tries to open the nonexistent virtual channel again.

Win7: netsh interface tcp set global autotuninglevel=highlyrestricted
http://blog.tmcnet.com/blog/tom-keating/microsoft/remote-desktop-slow-problem-solved.asp
I discovered that Vista's (Windows 7 as well) Receive Window Auto-Tuning could have issues on some networks. I really didn't want to disable Receive Window Auto-Tuning due to it's QoS, bandwidth speed/throughput, and VoIP quality benefits, but I had no choice. I use Remote Desktop all the time to manage 30+ servers. After disabling Receive Window Auto-Tuning, the "slowness" problem with mouse-clicks, keystrokes, and screen redraws went away.

2008R2: Major slowness, print related?
http://social.technet.microsoft.com/Forums/windowsserver/en-US/8b352070-8cdd-42f5-a0d7-13100e89c9c6/major-lag-performance-issues-win2k8r2-rdp
By the way, there is a tool called Process Monitor to show you the real-time information when accessing the application. That may show you a root cause why this application suspends.
Process Monitor v2.93
http://technet.microsoft.com/en-us/sysinternals/bb896645.aspx

Win7 / 2008R2: RDP Slow initial connection - Turn off Automatic Root Certificates Update
http://social.technet.microsoft.com/Forums/windowsserver/en-US/b8e58d83-3178-4490-b4f4-1c6e5542c39a/rdp-slow-initial-connection
This is an issue on networks that do not have access to the internet. I manage several different networks that are "dark sites" with no connectivity to the internet due to the highly critical and sensitive nature of them. All of them expirence this delay.

2008 RDP Sessions very slow Set TCPv4 Large Send Offload v2 - Disabled
http://social.technet.microsoft.com/Forums/windowsserver/en-US/289855a1-4861-426d-8de1-0200ab8e2670/rdp-sessions-very-slow
Large Send Offload (LSO) is a hardware off-loading technology. LSO off-loads TCP segmentation to NIC hardware to improve the network performance by reducing the workload on the CPUs. There are some similar slow performance issues related to this technology occurring, because the NIC hardware doesnt correctly response to this LSO requests. Based on my experience and research, the virtual machines encounter this issue more often.
In some cases, upgrading the NIC driver resolves the issue, because those manufacturers of the NIC has included the fixes into the driver updates.

2008R2 RDP Sessions Slow RDP Compression algorithm
http://social.technet.microsoft.com/Forums/windowsserver/en-US/5fa75908-663a-47ec-9038-dc44afb0d2bc/rdp-connections-suddenly-slow

Win7: Excruciating slow RDP into Server 2012 Hyper-V and its VMs
http://community.spiceworks.com/topic/337988-excruciating-slow-rdp-into-server-2012-hyper-v-and-its-vms
If this works then the issues is NIC related (perhaps an OS feature), but maybe down to the client drivers and settings and not the servers.
Made changes to each NIC that will be associated with OS Team for VM's, disabling VMQ.
re-created VM switch and seem to make an immediate difference.
No need to restart OS or anything
If not perhaps the issue is somewhere in the Host/vmnetwork, if it works fine, maybe something not NIC related, maybe at the physical switch level or the way the hosts NICs are being handled by the switch, it could be that teaming the hardware at server level is confusing or impacting something on the switch at the hardware level there.

2012: 2012 RDP Connection is slow - DisableTaskOffload in the IP-parameters
http://superuser.com/questions/515180/windows-8-server-2012-rdp-connection-is-slow
I don't see any warnings in the event log, and once connected, there do not appear to be any performance issues.