Problem solved! :-)
It was our virus scanner that interfered and suppressed a SMTP command! The crucial tip came from www.frankysweb.de/exchange-2010-error-503-5-5-1-smtp-bad-sequence-of-commands-smtp-error-503/ (in German language).
In the GData administrator, I only had to switch off checking the outgoing mail traffic, and everything works as before.