I was once contacted by one of our enterprise customers to troubleshoot a strange client-side PKI problem  – an email encryption certificate could not be issued for some specific PCs.
One of the problematic clients was a Windows 7 PC. Upon starting my troubleshooting session, I saw the “One of the CA certificates is not trusted by the policy provider” event.
This usually indicates that the Issuing CA’s certificate is not published in the NTAuth container of the Active Directory. In that case, the solution would be easy and we would just need to run certutil -dspublish -f IssuingCAcert.cer NTAuthCA so as to populate the container with the missing certificate. However, this was not the case, since most clients would successfully autoenroll for an encryption certificate – the problem was present only in specific PCs.

After digging some more into the registry, it was evident that something to that effect was happening – but this time, in the client-side PKI structure. Windows PCs cache whatever certificates are found in the AD NTAuth container at [HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\EnterpriseCertificates\NTAuth\Certificates]. This key would contain (cache) all NTAuth certificates which are propagated via group policy, which should also contain autoenrollment settings. What was found in the particular PC is that the client-side NTAuth cache was totally empty, which meant that either the NTAuth AD container
was empty (we rejected this based upon our previous observations) or the client could not successfully process its GPO(s). After running RSOP locally and opening the Group Policy Management console, we saw that the client was in an OU where the autoenrollment & encryption GPOs did not apply.
After we moved the PC to the expected OU and GPOs started “flowing”, the NTAuth client-side setting was populated and the autoenrolled encryption certificate was installed successfully.