There is a folder on device servers that seems to be holding the certificates before they are released to the devices.
C:\Windows\ServiceProfiles\NetworkService\AppData\Roaming\Microsoft\SystemCertificates\Request\Certificates
To fix the issue, I renamed the folder to backup > repushed the profile to devices > it will automatically create the "Certificates" folder. I renamed the folder on all the device servers and it has been working for us.
Good luck!