Du erstellst dir einfach einen eigenen. mail.foo.com als A record auf die IP, das nutzt du dann als mx.
Du musst lediglich einen A-Record anlegen der auf deinen Mailserver zeigt
mail.deinedomain.tld
das Ganze auf deine IP 0.0.0.0
Danach setzt du den MX Record der Domain auf mail.deinedomain.tld
lg.
Und wo lege ich den A-Record an? Und besonders: Wie? Ich habe sowas leider noch nie gemacht und kenne mich mit DNS nicht wirklich aus 
Das musst du mit Hilfe der DNS Funktion deines Domain-Anbieters machen.
lg.
Kann es sein dass ich erst irgendwelche Software auf dem Server installieren muss?
Hast du das Image mit vorkonfiguriertem Froxlor installiert? Dann sollte bereits alles fertig eingerichtet sein. Wie bereits erwähnt wurde muss ein A-Record für mail.domain.tld (oder alternativ ein Wildcard-Eintrag) gesetzt sein. Ach ja, und 48 Stunden warten nicht vergessen 
Hab das mit Froxlor vorintsalliert, ja, also Apache etc war auch schon drauf.
Ich kann bei dem Domain-Anbieter nur einen A-Record setzen. Wär ja auch... irgendwie quatsch zwei setzen zu können?!? Also muss ich was in Froxlor einstellen?
Danke für die überraschend gedulduge Hilfe 
Ich kann bei dem Domain-Anbieter nur einen A-Record setzen. Wär ja auch... irgendwie quatsch zwei setzen zu können?!?
Nö, es wäre Quatsch wenn man es nicht könnte. Jede Subdomain die du unterhalb deiner Domain nutzen willst braucht einen A-Record auf die IP des Webservers (so kannst du z.B. auch unterschiedlichen Subdomains unterschiedliche IPs zuweisen), bzw. in der Regel geschieht das indem man * als Subdomain verwendet, was für alle Subdomains gilt. Das müsste bei deinem Anbieter auch möglich sein.
[Blockierte Grafik: http://www7.pic-upload.de/thumb/09.03.14/rve5wgmw6i.png]
EDIT: Moment nehme alles zurück kann Subdomains anlegen und dafür dann extra A-Records machen. Da dann auch meine IP rein oder was muss dahin?
EDIT2: AHAHAHAHA ICH LIEBE EUCH ES GEHT! Danke
