Federation Trust Gateway broken - OrgCertificate cannot be uploaded

Hey guys,

last week we have done Windows Server updates and this broke some stuff. Some certificates have been unbound and so on. Until then the full classic hybrid worked quite good in our Exchange Server 2016 CU23 environment. We are just in the process of upgrading/migrating.
But after this point of time the On-Premises users stopped being able to see the calendars of the cloud users, other way around still worked.

So we started trying to fix the hybrid deployment with several runs of the HCW (which is always fine) and rebuilding the organizational relationship and the trust federation gateway. This was quite exhausting, as we updated a bunch of domains in global DNS several times. Currently, neither direction is functioning.

Now it looks like the Federation Trust Gateway is in an inconsistent state.

When I try...

Set-FederationTrust -Identity "Microsoft Federation Gateway" -PublishFederationCertificate

then I get the message, that the rollover certificate (OrgNextPrivCertificate) is not set and that I only can publish, when this is done. When I try to define a rollover certificate, then I get the message, that the rollover certificate cannot be set until the OrgCertificate has been published.

So, we have a chicken-and-egg situation here.

Thanks for any help.