This is not Exchange specific. A patch was applied to 2012, 2016, and 2019 domain controllers. Removing the patch listed below from the DCs resolved the issue for our network. This may be affecting other systems on your network. We have seen gpupdate failing on other systems throughout our network.
The affected patches:
kb5020023 - Windows Server 2012
kb5019964 - Windows Server 2016
kb5019966 - Windows Server 2019
"It's complicated, but it basically boils down to the RC4 bit being used as a signal of whether it should use a preferred cipher list or a legacy interop list in a specific section of code."
So, this update will break Kerberos for any computer that has RC4 disabled.
This is what Microsoft support is telling people to do instead of uninstalling the patch. It reverses the changes made by the patch.
Workaround from MSFT engineer is to add the following reg keys on all your DCs.
reg add "HKLM\SYSTEM\CurrentControlSet\services\kdc" /v
KrbtgtFullPacSignature /t REG_DWORD /d 0 /f
reg add "HKLM\SYSTEM\CurrentControlSet\Services\Netlogon\Parameters" /v
RequireSeal /t REG_DWORD /d 0 /f
reg add "HKLM\SYSTEM\CurrentControlSet\services\kdc" /v
ApplyDefaultDomainPolicy /t REG_DWORD /d 0 /f