Exim 4 connection timeout

I got a pretty strange problem with my Exim mailsserver recently.
Whenever I try to send mail to an emailaddress of a specific hoster (gmx.net) I get a timeout on the MX-Server from this hoster.

2012-01-19 11:34:56 1RnpHX-0005oz-0Y mx0.gmx.net [213.165.64.100]
Connection timed out

2012-01-19 11:38:05 1RnpHX-0005oz-0Y mx1.gmx.net [213.165.64.102]
Connection timed out

2012-01-19 11:38:05 1RnpHX-0005oz-0Y == [recipient]@gmx.de R=dnslookup
T=remote_smtp defer (110): Connection timed out

2012-01-19 11:38:05 1RnpHX-0005oz-0Y ** [recipient]@gmx.de: retry
timeout exceeded

Mail delivery to [recipient]@googlemail.com works just fine. And if I send an email from googlemail to the GMX-address it works aswell.

So what could be the reason that my server is unable to send emails to GMX?

PS: Just to mention it, I checked the RBL and my IP is not listed. The server I'm sending the mails from has a static IP and valid DNS records.