I am having the exact same issue and have done so for several months. Unfortunately I cannot remember exactly how many months, but it did start occurring after a Windows Update, I just didn't have the bandwidth to investigate it until now.
Exchange Server 2016 CU 21
Not sure what is related but here is what I have found so far.
Installed the following May Windows Updates (NB: There are no Exchange specific updates here):
2022-05 Servicing Stack Update for Windows Server 2016 for x64-based Systems (KB5014026)
2022-05 Cumulative Update for .NET Framework 4.8 for Windows Server 2016 for x64 (KB5013625)
2022-05 Cumulative Update for Windows Server 2016 for x64-based Systems (KB5013952)
I started receiving a lot of logon failures for x509 CN=smtp.gmail.com...
Then Installed the June Windows Updates:
2022-06 Cumulative Update for Windows Server 2016 for x64-based Systems (KB5014702)
2022-06 Cumulative Update for .NET Framework 4.8 for Windows Server 2016 for x64 (KB5014630)
The X509 Logon failures stopped, and instead I started getting "Host" Logon Failures the same as the OP in this thread