CBL This IP address is HELO'ing as "localhost.localdomain"

Solution 1:

As the page states, the HELO is not why your server is listed.

IP Address 93.190.139.208 is listed in the CBL. It appears to be infected with a spam sending trojan or proxy.

is why your server is listed. You'll need to figure out why it's being flagged as such and correct it.

Changing how your server identifies itself in the HELO is specific to the SMTP server that you're running. Can you give us a clue?

EDIT

Ok, got it. You have a couple of problems based on your edit:

1. CBL thinks you're spamming but offers no details on what exactly they're flagging you on.

2. It looks like atlantamail.com is rejecting your email because it can't validate the name your SMTP server is giving in the HELO command. You'll need to figure out where in Postfix to set the outgoing FQDN in the HELO and set it to something legitimate, such as hostname.mypublicdomain.com. If you send and receive email on the same server then it's easiest to set the FQDN to match your MX record and then you can create an SPF record that authorizes your MX to send email for your domain. None of these will guaranteee that your email will be accepted but will help.