I've found the problem, it's them!
They offer two domain names: gmx.co.uk & gmx.com.
I chose an address with gmx.co.uk which doesn't work for me.
I just took out the same address but using gmx.com and now it works fine!
So they have a problem authenticating their smtp server with a .co.uk suffixed address. (The pop3 server is fine with both domains.)
I'll now keep the one that works and cancel the original.
I'll let them know what's going on so hopefully they'll fix it.
Job done as far as I'm concerned, I'm no longer confused.com
Thank you everybody.