The same email sent directly from the sender address arrived.
Based on the above piece of information, there are two lines of investigation that are worth pursing.
One key difference between sending a message via CiviMail vs sending directly (i.e. from your mail program) is the "sender envelope from address", which is not the same thing as the "From:" address in the message itself. A CiviMail message uses a sender envelope from address using the domain in the mail account used for bounce processing.
i.e. look at [yourdomain]/civicrm/admin/mailSettings?reset=1 and look at the row that says "Used for bounce processing". All emails sent using CiviMail will use that domain in the sender envelope from address.
So, your first line of inquiry is to look at the SPF record of that domain and make sure that the machine that sends out the email has an entry in some form, i.e. that your smtp server ip is blessed to send out mail from that domain.
If that has already been done properly, then the second line of inquiry is to look at the IP of your outgoing mail machine and look at it's reputation. It's possible that GMX is using a blacklist to block email from your mail machine's ip.
If both of those seem like issues that are too technical, then you really will need someone who understands them to sort it out, otherwise you won't be getting much value from CiviMail.