Look at the key points on the SBL pages: "Can't trust this IP space at the moment."
At the moment. I would suggest leaving that /24 IP idling for 1 ~ 3 months. Explain to the VPS customer your circumstance and the need for an IP change (I'm aware and admit that this is actually sounds easier than doing it). After that, you can contact them again to remove the listing. State that the IP has been cleaned from the abusers and not being used for some months already (in a non-aggressive way). Then ask them politely if there's any additional steps or information needed in order to remove that listing. They might go on defensive mode again if your tone is deemed a bit aggressive by them.
The goal here is to get the IP delisted. Questioning and making a problem of their decision, even if you're in the right, might not yield a good results.
If you do it right, it should work. Source? I'm not authorized at the moment to disclose the source info