Mail delivery problems are a pain to deal with. We've created this six step walk through to make getting removed from RBLs a little bit easier.
What is an RBL? An RBL or Real-time Blackhole List is a listing maintained by a 3rd party company of IP addresses and domain names that have been reported as spam sources. This doesn't mean that you are sending spam, it means that your server was reported as a spam source. Legitimate mail senders can still get listed if they do not have the correct records set up or have an exploited website or server sending out spam.
Before attempting to be delisted, you should see if there are any exploited sites or programs on your server that could be sending spam. If you don't remove them, your server will be listed again on the same RBL, and they may not allow you to be delisted in the future.
After identifying the problem, you should take steps to resolve it. This means removing exploited scripts/plugins/files and cleaning up websites. Again, if you're not sure how to do this, you should reach out to your system administrator.
Once you've checked for problems, you should make sure that your records and configuration are correct.
In general every domain that is sending mail should have the following records: SPF, DKIM, DMARC. These three records tell other mail servers that you are a legitimate sender when sending from your server, and what to do with mail sent from other servers claiming to be you.
If you need help setting up those records, here are some guides that will help you get started:
Creating DKIM Records in cPanel
Creating SPF records in cPanel
You should also ensure that your mail server has the correct hostname, and that your reverse DNS record (PTR or rDNS) has been set up. Ideally your rDNS record should match the domain you are using to send mail or it should match the hostname.
Now that you're confident you aren't sending out any spam and your records are correct, you can scan to see what RBLs you are listed on. One tool for this is MxToolbox blacklist checker. This site will scan your IP address against the most commonly used blocklists.
If you are listed on Gmail, Yahoo, Hotmail or other providers like this, they do not have a publicly scannable listing, so the only way you would know you are listed is if you see a bounceback. Make sure to always read bouncebacks messages when mail delivery fails.
You should also check Senderbase to ensure that your IP has a good reputation.
Now that you know where you are listed, you can request a delisting. Included below is a list of links you would need to use for some of the mail providers that don't provide public listing checks.
Link to Gmail, Hotmail, Yahoo and other similar delistings
If you scanned on MxToolbox, you can use the links provided there to get delisted.
After submitting the requests, if you are still have trouble with listings, you should review the mail transaction logs. Anytime you send out an e-mail, the recipient server will accept, reject, or defer the mail. Whatever the response, the recipient server will notify your server what it decides to do and if it's a defer or a rejection, will usually tell you why.
The main log you want to check is /var/log/exim_mainlog but you can also use the WHM delivery logs if you are using cPanel.