Hallo,
folgendes kommt in Betracht:
a) der PTR ( ReverseDNS) Record schuld, einige Blacklisten erkennen hier wohl eine dyn. IP.
Dieser kann per Kundencenter -> IP-Addressen geändert werden. (Der Mailservername muss dann auch entsprechend aktualisiert werden)
b) Der Mailserver ist falsch konfiguiert (offenes Relay) , es wird Spam versendet etc.
Genaues kann man bei den Blacklisten normalerweise erfahren, bei einigen ist hierzu eine entsprechende, meist englische, Anfrage nötig.
Gruß Timo,