active directory - RDP presents Self-Signed certificate instead of Certificate Authority's one

Few days ago I witnessed a strange problem within my domain:

• During RDP connection I see warnings about certificate being not trusted (and I see self-signed certificate, not issued by domain CA)




• I can no longer connect by RDP to servers with enabled NLA (Network Layer Authentication).

This problem is omnipresent - I experience it on different workstations and on different servers, including Windows Server 2012R2|2008R2, Windows 7 and Windows 10.

About CA infrastructure: one offline Root CA and one Domain Level Issuing CA. pkiview.msc says everything is OK: both Root and Issuer have valid Certificates, CDP's, IAI's and DeltaCRL's (issuer only). I've updated Root CRLs and republished them in AD because I thought that might be the case but no luck.

Custom Certificate Template with Client|Server|RDP Auth still exists and I can confirm that servers in question have such certificates in Personal folder in MMC Certificates Applet (and can request new ones from there), although only self-signed certificate is present in RDP folder.

Using MMC Certificates applet I also see that both Root and Issuer certificates are trusted.

So.. I don't really know what to do and how fix it, and why it's broken in first place. Any help is appreciated.

PS. Also some time ago I modified Default Domain GPO enforcing private network IP ranges. Can it be the reason? Anyway, I turned those back to default and no luck either.

UPDATE
Some pics to clarify a bit:

1) Security Warning

2) ...because servers presents Self-Signed Certificate

3) However we can see proper CA-certificate in Personal storage on server in question

4) In Remote Desktop certificate storage I can see just Self-Signed Cert. I copied proper one there as well, but no effect. And if I delete Self-Signed Cert from there I won't be able to connect to server over RDP at all.

5) Also you can see that my local CAs are trusted by server:

6) And that is the error I get when I try to RDP to NLA-enabled server. So client for some reason can't or won't willingly use CredSSP. It worked a week before so I think it's connected to cert problem.

7) Finally some screens from Issuing CA. It seems to be OK.