Sorry for the late reply
I was wrapping things up to come up with a final solution
So here are the steps I took to resolve my issue:
1 - Delete the old cert manually from problematic devices (and later from non-problematic devices to be on the safe side)
2 - Do as @AllenLiu-MSFT mentioned:
- Stop the Windows Update service by running the following command: net stop wuauserv
- Rename the C:\Windows\SoftwareDistribution folder to C:\Windows\SoftwareDistribution.old.
- Start the Windows Update service by running the following command: net start wuauserv
3 - Reinstall the client by pushing it from the site server and checking (Uninstall current SCCM client)
Thank you @AllenLiu-MSFT , your note definitely helped