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.