Further, you can use https://mxtoolbox.com to help validate that the record are correct and the IP you have is not on a black list.

You’ll either need to track down the operator of the blacklist and tell them it’s no longer a spam address or, get a different IP from a different provider.

Additionally, to stay off black lists you’ll need to lock down you relay feature so that only mail you want is going out. I.r. don’t allow an open relay from anyone, if you have users, you should throttle them, and probably do outbound spam filtering to protect your IP in the event they use a bad password or something.