I’ve moved to Office 365 for my private mails a while ago and. Up to now, the provider hosting this website was responsible for the DNS entries. But now I moved the entire DNS authority to Microsoft for my primary domain. This lead to the unfortunate incident that I was unable to send mails to GMX (one of the largest free mailer in Germany). Thanks to a tip from Daniel Melanchthon I was able to resolve the issue fairly quickly.
The problem seems to be that GMX checks for the existence of a DNA A record on the sender domains. My primary domain is henningkrause.eu. When I send an email to GMX, they check for an A record for henningkrause.eu. I’m not sure why they do that - I know of no RFC which makes such a record mandatory. The A record is normally only used as a fallback method in case no MX record can be found. The solution was to create such a DNS record using the Office 365 DNS management interface:
The entry in question is the one highlighted in red. The host name "@” specifies that the A record is to be created for the domain itself. The interesting thing is that it is not relevant to which IP address the A record points. It just needs to be there. If you experience the same issues and don’t have your own website, just point it to any IP address.
After I created the domain, I was able to send mails to GMX again almost immediately.