Das sieht zumindest für gmx nach diesem Problem aus:
web.de sperrt yourvserver.net als rDNS
Um das zu fixen musst du im CCP in der Config deines Servers (nicht in der von der Domain, da hab ich etwas Zeit verschwendet) als rDNS den Domain-Namen deines Mailservers eintragen.
Das bezieht sich glaube ich nur auf eine Neuinstallation oder?
Das stimmt. Das Standard-Image habe ich mir nicht angesehen, da kann es natürlich anders sein. Habe direkt neu installiert, da ich ein anderes System wollte.
Woran könnte es noch liegen?
Es dauert eine Weile, bis die Änderung des rDNS in allen Caches angekommen ist, so weit ich weiß bis zu 24h. Bei mir war es z.B. so, dass einige der Server von gmx die Mails schon angenommen hatten, andere noch nicht. Bei mir war der Spuk allerdings auch nach knapp 1h zuende und alle Mails aus der Warteschlange waren durch.
Sonst lass doch mal einen Mail-Server-Test über deinen Server laufen, der zeigt die häufigsten Fehler schonmal an, z.b. Email Server Test - Online SMTP diagnostics tool - MxToolbox
Klar kann man auf der Netcup Seite noch dazu schreiben wie das Standart Image partitioniert ist, jedoch ist es glaube ich nicht zu viel verlangt den Befehl df -h einzugeben um etwas Licht in die wichtige Sache zu bringen.
So weit ich weiß, fragt bei den Images der Einrichtungsdialog auch nach,
ob man die ganze Partition nutzen möchte. War bei mir zumindest kein
Problem, ich habe aber auch vorher alle Anleitungen im Wiki durchgelesen, da ich zwangsläufig etwas Bedenkzeit vor der Bestellung hatte 
Ist das bei diesem Angebot überhaupt möglich, ihn zu übertragen? Wenn ja, kostet es laut Wiki eine Bearbeitungsgebühr: Wechsel des Inhabers – netcup Wiki
Aber ist der Unterschied virtuell vs. dediziert wirklich die 1€/Monat Ersparnis wert oder nimmt man den Vorteil lieber doch mit?
Ich habe besagten Root M mit vCores und für meine Anwendungen reicht es dicke aus. Bei mir läuft (alles Größenordnung <10, also nix aufregendes) Mailserver, ownCloud, Mumble, Jabber und ein paar kleinere Scripte, und der Server langweilt sich die meiste Zeit vor sich hin.
Bei mir (Vorbestellung am Nachmittag) kam bisher nur eine automatische Eingangsbestätigung.
Solltet ihr euch für einen root-Server entscheiden, dann wäre es wegen des Speicherplatzes vermutlich Größe M aus der aktuellen Generation. Dann würde ich an eurer Stelle gucken, ob ihr noch von diesem alten Angebot einen nehmt:
Der ist im Vergleich zum "normalen" Root M 1,50€ pro Monat günstiger, hat weniger CPU-Leistung (vCores anstatt dediziert) und keine Snapshots und keine eigenen Images. Von der Leistung her reicht der definitiv aus.
wo schreibt man was dazu rein? Hat das jemand gerade handy?
In die postfix main.cf (NICHT master.cf). Wo die genau liegt, hängt von deiner Installation ab.
Hmm... Auf dem Auge war ich tatsächlich blind... Hatte mich durch die allgemeine DNS-Doku im Wiki gewühlt, nicht auf die FAQ geguckt... Danke
Es liegt wirklich an dem Hostname. Ärgere mich gerade wie wild, weil ich leider keine Information dazu bekommen habe und meine gesamten Mails noch im Queue rum hängen. Gibts da vielleicht eine gute Lösung das zu beobachten, damit man das nächstes Mal besser handhaben kann?
Ich bin auch über denselben Fehler gestolpert. Bei mir war zum Glück nur eine Hand voll Mails betroffen und es ist mir relativ schnell aufgefallen.
Postfix hat eine Option "delay_warning_time", die den Sender benachrichtigt, falls eine Mail zu lange hängen bleibt. Das wäre m.M.n. eine sinnvolle Lösung, wenn du außerdem noch "delay_notice_recipient" auf eine Adresse setzt, die du überwachst. Dann solltest du diese Meldungen auch noch bekommen, wenn ich die Doku richtig deute: Postfix Configuration Parameters
Dasselbe ist mir auch passiert, auch seit letztem Wochenende. Bei mir war es einfach Unwissenheit, ich hatte irgendwie erwartet, dass ich den PTR in den DNS-Einstellungen im ccp mit setzen kann. Ist logisch dass es beim Server ist, war aber für mich verwirrend.
Vielleicht sollte da ins Wiki ein kleiner Hinweis auf die DNS-Seite, wo man den rDNS-Eintrag setzt?
Was mir an der Telefonverifikation aufgefallen ist: Es ist nur ein kleiner Plausibilitätscheck. Ich weiß nicht ob es immer genau so läuft, aber bei mir wurden nur die eingegebenen Daten abgefragt (die ich als potentiell böser Mensch ja auch wüsste, weil ich sie eingegeben habe) und es wurde eine Frage gestellt, die ich mit rudimentärem Wissen über meinen Wohnort (wahlweise auch zügiges Googlen) hätte beantworten können.
Effektiv wurde also "nur" die angegebene Telefonnummer auf Existenz und Zugang meinerseits getestet.
Das reicht natürlich als Plausibilitätsprüfung, aber mehr ist es eben nicht.
Ich nutze einen Root-Server M (allerdings die Angebots-Version mit virtual CPU und ohne Snapshots) für einen dovecot/postfix-Mailserver mit Roundcube-Webmail, eine ownCloud und noch etwas Kleinkram (kleiner xmpp und mumble). Die Dienste sind jeweils in derselben Größenordnung wie bei dir, also <10 Nutzer. Der Server langweilt sich größtenteils vor sich hin, ausschlaggebend waren die 240GB Festplatte, dass ich den und nicht den Root S genommen habe. Der Mailserver ist das harmlosere, für den alleine hätte ich keinen Root M angemietet.
