Hola, si eliminando los certificados del registro no te funcionó intenta lo siguiente:
1) Ejecuta tscc.msc y elimina la conexión RDP-tcp
2) Reinicia el servidor
3) Ejecuta tscc.msc y crea una nueva conexión/listener RDP-tcp por defecto.
4) Reinica el servidor
Espero te sirva la info.