Hello,
We are having the exact same issue on a Windows Server 2008R2 with Outlook 2016 since a few days.
We tried to enable TLS 1.2 but unfortunately without any luck.
It is indeed working on a different server from within the same domain. (SBS 2011, same build as the 2008R2)
Last year we migrated the On Premise Exchange to M365 with success and this was all functioning well untill a week or so.
Autodiscover is not the problem because it works on different servers from within the same domain with the same DNS configured.
Also, it fails when trying to add an e-mailaccount from a different domain.
It indeed looks like it has something to do with the client certificate. I have the same error as OP. "We couldn't authenticate your client certificate"
I have downloaded the updated certificate list and imported this in our certificate store, without any luck.
certutil.exe -generateSSTFromWU C:\PS\roots.sst
After executing this commando I imported the list MMC > Certificates (local computer) > Trusted Root Certifiations > Right Click Certificates > Import > roots.sst
(We do have Modern Authentication enabled on M365 & Server side)
Best Regards,
Jelle