So I changed my Domain, I added a new rDNS Record and a new @ for the Domain.
I then restarted the whole machine to make sure everything is changed (Hostname included)
But for some freaking reason the mail server still tries to send messages over the old Domain which makes it undeliverable. Is there any way to change the Hostname in the Mail-Server Software?