Das kann an ziemlich vielem liegen. Kann am DNS-Server liegen (wobei der in diesem Fall die Infos auch nur ziehen und cachen und nicht verändern sollte), es kann aber auch an den Einstellungen des Mailservers liegen. Was sagt denn der NSLookup type=mx? Und wenn das geht, kannst Du vom Mailserver her ein Telnet auf Port 25 des Zielservers durchführen?
Blacklist-Eintragungen sind genau dann tragisch, wenn der Empfänger genau diese Blacklist benutzt. Also reagieren und schauen, wie man aus der Liste wieder rauskommt, und vor allem auch, warum man da reingekommen ist und das Loch stopfen.