Authentication to SMTP as some domain user <user>@<domain> keeps failing when the domain is other than the host name (or the domain that was created at installation time). The message on the server is:

Oct 10 17:20:45 host saslauthd[11583]: auth_zimbra: <user> auth failed: authentication failed for <user>
Oct 10 17:20:45 host saslauthd[11583]: do_auth : auth failure: [user=<user>] [service=smtp] [realm=<domain>] [mech=zimbra] [reason=Unknown]

This happens with TLS set on & off in SMTP authentication on the server. Restarting saslathd as suggested in another forum thread didn't help either

Authenticating as any user of the hostname domain works fine.
Sending & receiving from the web interface works fine for all domains.

Is this a DNS issue? Any hints so I can investigate it further?