If you haven't already, you will need to identify each and every blacklist that your IP addresses are on, and then use their de-list forms to try and remove them from their lists. For example, I see you have found your IPs on V4BL...you would need to go to
http://c92.v4bl.org/delist/ and enter the IPs to remove them.
I see that you said you had no success in removing your IP addresses from the blacklists...if you have tried the de-list forms and not had any luck, meaning your request has been declined (it can take a while) - then most blacklists have email addresses that you can contact to plea your case. V4BL's are
[email protected] and
[email protected]. Make sure to mention that you have recently acquired the IP addresses so as to remove yourself from any previous negative activity associated with them.
Finally, if OVH (I assume you mean the French web host) provided you with the IP addresses in question you should contact them and let them know that their network appears on the blacklists - they might be inclined to help you out.