Problem wurde bei uns wie folgt behoben:

Der MX zeigte zwar innerhalb unserer Domain auf einen A-Record, dieser war aber beim Mailprovider wiederum ein CNAME. Hier handelte es sich wie bei Christian um den in.mx.trendmicro.eu
Nach Umstellung auf den dortigen A-Record (in.eu.mx.trendmicro-fail-over.akadns.net) dauerts keine zwei Minuten und die Mails an 1und1 können zugestellt werden.

–> SPF musste nicht gesetzt werden!

Ich versteh nicht, wie die grossen Provider immer wieder auf die glorreiche Idee kommen, einfach solche Änderungen ohne irgendwelche RFCs oder Ankündigungen durchzuführen. Antwort von meinem Provider: „ja, die sind halt gross genug, das alle anderen einfach nachbessern müssen“.
Ich mein… CNAMEs sperren? Hallo? Gehts noch?

Viel Glück euch da draussen