Solved!
@Osiris & @rg305 thank you for the hint!!
I added an A pointer which points to my servers subdomain "mail" (as my others subdomains www etc.) to the account at my hoster.
That was it, pretty easy!
Looking back I had forgotten the "mail" subdomain when I set up the subdomains at my hoster.