Exim – block incoming mail from blacklisted IPS only

Modern major mail services score spamminess based on multiple reputation factors, if available.

If the only factor is your IP and you don't mail often, this might be "the reputation of the /24 my IP is in". If you mail a lot, you might get your own reputation.

The easiest way to get reputation which "drowns out" the IP reputation of your netblock is to set up DKIM. Send your mails signed. This will establish a per-domain reputation, instead of per-IP reputation, and provides more signal to the automated scoring systems.

The more you work to help the recipients of your email figure out who you are and how trustworthy you are, the more signals they have to work with and the better a job the automated systems can do in deciding that you're legitimate, unlike whoever else bought a virtual machine in the same netblock, pumped out spam and then left, bills to hosting service unpaid and everyone else's reputation tarnished.

[some years later]: I wrote a blog post a couple of years back, walking through a lot of the steps needed to be able to more reliably send to large mail providers: https://bridge.grumpy-troll.org/2020/07/small-mailserver-bcp/

Fix your mailserver, ensure you don't make faulty setup again that will allow relaying. I advise you to check own mails for spam too to ensure some of your own users don't spam either deliberately or if their mail account gets stolen and thief uses it to legitimately tries to spam from your server.

When that is done, change the ip of your mailserver to other IP available, adjust DNS records, to reflect the IP change.

You can force that mails are sent from other IP with SNAT rule in iptables

iptables -t nat -D POSTROUTING -j SNAT -p tcp --dport 25 --to ot.her.ip.address

extra: add SPF field in zone that will confirm new IP is legit source to send mails for domain(s) Add DKIM filter to sign mails.

oh, and If I may suggest to try replacing exim with postfix