In the following I explain my steps of getting a vServer and starting to use it.
(on the responsible Nameserver)
mydomain.tld. 86400 IN MX 10 mail.mydomain.tld.
mydomain.tld 86400 A 0 123.123.123.123
mail.mydomain.tld 86400 A 0 123.123.123.123
*.mydomain.tld 86400 A 0 123.123.123.123
mydomain.tld 86400 AAAA 0 FE80:0000:0000:0000:0202:B3FF:FE1E:8329
mail.mydomain.tld 86400 AAAA 0 FE80:0000:0000:0000:0202:B3FF:FE1E:8329
*.mydomain.tld 86400 AAAA 0 FE80:0000:0000:0000:0202:B3FF:FE1E:8329
mydomain.tld 86400 TXT 0 "v=spf1 mx a a:otherdomain.de -all"
Explanation: This record allows to sent mail from the server referenced in the A record and MX record as well as the server mentioned in the A record of otherdomain.de, mail from any other server should be rejected! (See Wikipedia/SPF, SPF Wizard) To test your SPF setup use: http://tools.bevhost.com/spf/ and http://www.kitterman.com/spf/validate.html
server1.mydomain.tld