Ich habe seit ein paar Tagen das gleiche Problem festgestellt (mx*.kundenserver.de). Vielen Dank fuer dieses Blogposting – es hat mich auf die richtige Faehrte gebracht.

Weiteres rumsuchen ergab dann, dass MX records in der Tat A (or AAAA) records sein sollten, und nicht ein CNAME (siehe auch http://www.exchangepedia.com/blog/2006/12/should-mx-record-point-to-cname-records.html und die daraus verweisenden RFC Referenzen).

Nun ist es bloss seltsam, dass sich bei mir das ganze seit Jahren nicht geaender hat, und nun wirklich ~alle anderen mail server da kein Problem machen.

Nun gut, DNS updated, warten bis das propagiert und dann mal weiterschauen…