Every time you are sending an E-mail, it goes through your SMTP server. It's like your town's post office. But Hotmail is receiving a lot of spam from that SMTP server. So they have decided to reject it, even if it kills legitimate mail.
So it's a deal between your mail provider (GMX?) and MSN/Hotmail. Write GMX and tell them about this issue.