DigitaOcean sold us a droplet with a blacklisted IP. How do we get another IP?

Hello,

About 2 months ago, we purchased a DigitalOcean droplet. We moved our customers websites and email server in there.

To our great dismay, the droplet IP address “looks clean” for some major spam email IP blacklists but not all. Our customers are unable to send email to Hotmail, Live.com, Outlook.com and to the second biggest national email provider in our country.

Microsoft is taking weeks to “evaluate” the blacklist removal and that email provider is totally unresponsive (actually, its third party “email reputation service” is).

So we have 70% of our customers unable to do business and very annoyed with us.

What can we do?

Every other VPS provider sells additional, hopefully “clean” IP addresses but not DigitalOcean.

I thought about saving a droplet snapshot, destroy the snapshot and then rebuild it again, but I just read that, if when we’ll rebuild the server we’ll get back the same, blacklisted IP.

Is there any option to force in another IP address?

Please help us, we hoped to save time and money with DigitalOcean but we’ll probably end up losing hundreds euros to idemnify our customers!