So, seems like Microsoft's *.olc.protection.outlook.com mail servers are currently using certificates signed by an distrusted root CA[1].
That seems like a shocking level of incompetence.
It means that any mail server supporting MTA-STS is currently unable to deliver any mail to them.
[1] DigiCert Global Root CA which has been scheduled for distrusting since 2023 https://knowledge.digicert.com/general-information/digicert-root-and-intermediate-ca-certificate-updates-2023