When we send mails to AOL accounts, they are rejected and bounce back. After checking our IP on blacklists, there seems to be two lists on which our IP appears blacklisted. This comes as a surprise to us as we never spam and only mail our clients when necessary.
I have contacted our hosting provider and they are trying to delist our IP from the blacklist.
Is this realistically achievable, i.e. how do hosting providers go about doing this?
With many hosting companies, it is common that they do not manage their IPs reputation. This means that you can buy a new server and get a dedicated IP address which has a bad reputation because the previous customer of the same hosting was sending spam or had an infected machine.
Delisting procedure is specific to each blacklist. A good summary is provided in this blog post How to Get Removed from Blacklists.
In short, it really depends on the blacklist owner if and when you are going to be removed after you (or your ISP/hosting) request removal. Some blacklists are not even free to remove instantly.
With every new IP we obtain with a new server, we always go with a check immediately and setup blacklist monitoring. If there are problems, we try to ask for removals and if it is not possible, we ask for different IP address. This prevents later surprises.
Moreover, some email providers (Microsoft's services like Hotmail, Outlook; Yahoo, AOL) are known to be very strict and actually require a perfect reputation history of the sender in order to deliver all the emails. It happens often with these services, that you try to send email to an account there and it is discarded silently.
