Mirela_Buru I will go away from here, (not doing a user voice though). But first, I can't not clarify something. It is AFTER you've already renewed the org certificate that I'm referring to. Maybe what you are telling me is that we need to nullify the OrgPrevPrivCertificate property on the Federation Trust? That is the other part of the undocumented / unsupported process which I was alluding earlier. You blank that, and then manually cleanup by deleting the old cert from all the Exchange servers.
The "current design" does not have a solution for when the certificate specified in the OrgPrevPrivCertificate has expired. When it happens, the Federation Trust does not have to be rebuilt. But you will get notifications in ECP and in Event Viewer that the certificate has expired. Here's an example of real life customers experiencing the issue: https://social.technet.microsoft.com/Forums/en-US/f5349498-df20-4cea-a565-bd544ed56b0a/how-to-remove-previous-federation-gateway-certificate