GMX seems to throw the 'registration unsuccessful' message up when it doesn't like the IP address that you're using. It's known, for example, to reject account applications from people who're using the Tor network to hide their real IP addresses. (However, once an account has been obtained, it can then be accessed normally over Tor, or from any other IP address).
It's possible that your IP address is blacklisted as a source of spam because your ISP previously allocated it to a spammer. So you could try changing it. To do so, start by checking your current IP address here:
http://whatismyipaddress.com/
Disconnect your router from your phone line, wait a minute or two, then reconnect and go to the link again to check that you've got a new IP address. Once you've done that, have another go at creating a new GMX account.
It might also be worth going into your browser's setting to check that your internet traffic isn't being sent via a proxy server. (Some browser extensions do that without you necessarily knowing about it). In Firefox you click the 'Tools' button (three horizontal lines, top right) and then Options > Network > Advanced > Settings > No Proxy > OK. There should be something similar with most other browsers.
I had repeated 'registration unsuccessful' problems with a new GMX account recently but overcame them by changing my IP address.