Great to know that the issue has already been resolved and thanks for sharing the solution so that others experiencing the same thing can easily reference this! As I suspected it could be related to a certificate issue, unfortunately my method didn't help you directly. Since the Microsoft Q&A community has a policy that "[The question author cannot accept their own answer. They can only accept answers by others] ", I'll repost your solution in case you'd like to "[Accept]" the answer : )
--------------
Issue Symptom:
The Out of Office messages sent to external recipients won't be delivered anymore with Relay Access Denied error.
Resolution:
The Outbound Connector towards internet needs an SSL certificate nowadays. In specific case, you could use the same certificate as what you did on Hybrid Connection, even though you do not require TLS on the connector.
As soon the certificate was assigned and FrontEnd Services were restarted Outbound queued Out of Office mails got sent again.