X-Matching-Connectors exceeded allowed maximum

When sending some mails from Postfix to Outlook365 i receive an error:

Nov  1 08:00:00 mail postfix/smtp[16252]: B7E8079FA8F:
to=<somemail.dk>,
relay=somemail.mail.protection.outlook.com[104.47.7.138]:25,
delay=0.71, delays=0.06/0/0.1/0.55, dsn=5.6.211, status=bounced (host
somemail.mail.protection.outlook.com[104.47.7.138] said: 554 5.6.211
Invalid MIME Content: Single text value size (32784) exceeded allowed
maximum (32768) for the 'X-Matching-Connectors' header.
[FR3P281MB0970.DEUP281.PROD.OUTLOOK.COM]
[AM6P192CA0016.EURP192.PROD.OUTLOOK.COM]
[BE0DEU01FT017.eop-deu01.prod.protection.outlook.com] (in reply to end
of DATA command))

To avoid this i have tried to strip all X-Matching-Connectors from my mails, but the this does not solve the problem, a matter a fact it seems like the outgoing mails does not have this header at all (i use postfix header_checks to remove another header just to make sure it works, and i can se this is removed in the log).

I also cannot find any info on the X-Matching-Connectors anywhere. Anyone know what it is and maybe where it is added?

How can I solve this problem?

Only found this online: https://answers.microsoft.com/en-us/msoffice/forum/all/getting-ndr-from-some-servers-headers-too-large/a3ace969-9d08-4d07-967a-5f40f9a0bad7

UPDATE == 5-11 ==

I have tried to set header_checks up to log ALL headers in the outgoing mail, and the offending X-Matching-Connectors is not send from Postfix to Outlook. Maybe its a header being generated in the Microsoft mailserver?

Further info : Our Postfix server is also on a Linode server (as M Klein, below). But running as a standard mailserver.

Answer to comments:

Yes, the Postfix mailserver has worked for years without this problem, and can send to gmail and other servers without issues.

Yes, I can send to the receiver from fx gmail without issues.

No, it does not seem to be all email to office365 which have this issue, only some recipients/domain. But its all mails send to these domains.

Related info:

https://social.technet.microsoft.com/Forums/office/de-DE/8d08697c-c0fc-449f-88ca-c92c4e75b3d3/fehler-beim-senden-an-office-365-server?forum=office_generalde

https://www.linode.com/community/questions/22063/anybody-having-issues-sending-mail-to-exchange-online-domains-from-european-loca

UPDATE == 24-11 ==

The problem seems to be related to how the mails are encoded. At lease in a test script I made.

no multipart AND charset utf-8 : FAILS (allowed maximum (32768) for the 'X-Matching-Connectors' header)
no multipart AND charset us-ascii : WORKS

multipart AND charset utf-8 : WORKS
multipart AND charset us-ascii : WORKS

Solution 1:

We have also seen this from some of our Linode mail relays.

The problem we've found seems to be down to sending mail from European relays to Microsoft 365 accounts also hosted in Europe. If we route mail to them via the US we don't see the bounces.

We've raised this with Microsoft and have a ticket outstanding with them.

Other linode users are seeing this too https://www.linode.com/community/questions/22063/anybody-having-issues-sending-mail-to-exchange-online-domains-from-european-loca

The problem does not seem to be down to the MTA talking to Exchange (e.g. postfix). Using openssl s_connect to manually make a connection and send a minimal email also results in the same NDR.

We have found that sometimes mail can get through and the X-Matching-Connectors header is there (consisting of a lot of UUIDs).