Being blacklisted is certainly not a pleasant experience. Here is more about blacklists in general, how you can check if you really got blacklisted and what you can do in order to solve the issue:
An introduction to blacklistsDistributed Mail Blacklists are databases used by different systems to decide if the IP connecting to a certain mail server is a known spammer/pharmer or one known to send invalid messages. These systems aim to improve mail security and integrity and most of them are community managed. If you (your mail server's IP) are listed in any of these databases and you try to send an e-mail to a server that uses that particular database to filter spam, you will find out that you cannot send e-mails to that host.
Another kind of blocklist/blacklist is the local list that can be used by any mail server administrator. The removal from such listing requires contacting the local administrator directly, by the usual means, e-mail or phone.
Knowing if you really are blacklistedThe most straight-forward method to find out if you are blacklisted is to look into the log file and establish the reason why your e-mail did not get delivered. Usually, servers enforcing Real-time Blacklists, DNS-BL, or RBL using a blacklist database will reply to your send request with an error message stating this particular event. In addition, most of these error messages also contain further details and, in many cases, a direct link to the site of the blacklist or to your particular IP details in their database. This second type of link provides you with details about the reason why your IP was added in their database and who submitted the request to block your IP, as well as the ways to get removed from the blacklist.
You must make sure to correctly identify the blacklist message. If you do not find such a blacklist entry in your logs, and still cannot connect to port 25 on a certain host, you should attempt a telnet connection to the server's port number 25 with this command:
telnet mail.example.com 25In the case this command returns a “timeout” or a "connection refused" message, then you have encountered a connectivity problem, and you are not blacklisted. Another situation when you might be tempted to conclude that you have been blacklisted is when you receive a "deferral message". Such messages are used to prevent a large quantity of SPAM and they are based on the fact that spammers do not try to resend their messages if they are blocked or refused. Such a deferral error in your logs does not mean you are blacklisted. Your server will resend the message and it will ultimately get delivered. You can also prevent this behavior by reporting your IP to the administrators with complete details to prove that you are safe to be permanently added on their accept lists.
Lastly, you can use any of the blacklist search engines available on the Internet to lookup your IP/hostname. These sites search a number of blacklists to find out if you have been blacklisted by any of them. If you decide to use this approach, you should consult more than one blacklist search engine to make sure you cover as many blacklists as possible.
Clearing your nameMost of the times, you can remove your IP from any blacklist by visiting their site and submitting a removal form, after having filled in all the suggested details. Such information may include proof that you have ceased any actions that got your IP blacklisted in the first place, or may not require anything but your mere interaction, to demonstrate that you are not a robot or a script.
If the entity that blacklisted you does not have such a removal form on their site, you will need to send an e-mail to the abuse account or, when this one is also missing, to the postmaster/root. You can also try searching their site for contact information or any details related to blacklisting. It is fairly important to note that while being blacklisted is very frustrating, you should use a cordial tone in your e-mails. Always remember to be respectful and patient. Being removed from a blacklist can take some time and there is nothing you can do to speed up this process other than being as patient as possible.