Remote Desktop cannot verify the identity of the remote computer because there is a time or date difference between your computer and the remote computer

I had an issue with a server that was failing to connect over RDP with the following error:

Remote Desktop cannot verify the identity of the remote computer because there is a time or date difference between your computer and the remote computer

On inspecting the machine via PSremoting, the clock time showed fine. I thought I would try connecting to RDP using the IP address. That let me through with only the normal certificate mismatch warning prompt. Looking around for solutions online usually pointed to the obvious clock problem in the error message. But again, clock time was perfectly in sync and timezone was fine as well. Another possibility given in some people's posts on this topic is the RDP certificate itself. This is located in the computer's certificate store under remote desktop\Certificates. This is automatically generated by the machine and will be recreated if deleted. I checked that, and again no issue with the certificate dates.

After digging around in the registry in HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Terminal Server\WinStations\RDP-Tcp, I found a discrepency between this machine and another working machine. My broken machine [freshly build] had the Security value set, while the other didn't. (https://support.microsoft.com/en-us/kb/259129) Additionally this didn't match the defaultsecurity value one level up. After deleting the value and rebooting, the issue went away. Trying to reproduce the problem by putting the same value back in place only gave me the error once, then continued to let me through. So this may be something to look at if all else fails.