MP-9510 I had issues receiving emails from exchange servers specifically like you were. It was due to the MX record in DNS pointing to a CNAME record. It seems Microsoft may have implemented a stricter reading of an RFC and the MX record needs to point to A / AAAA records. That was the missing piece for me.
i.e. If your MX record returns mail.<your-domain>
and mail.<your-domain> is a CNAME record for <your-domain> or any other address
then mta-sts validation will fail.
Resolving mail.<your-domain> MUST return an A and/or AAAA record.
Sources:
Introducing MTA-STS for Exchange Online
Clarifications on MTA-STS Policy with CNAME Records