I'd recommend contacting your provider which will probably contact their data center(if you are not hosted directly from a provider who owns their dataceter/collocates there). It's their responsibility to keep their IP ranges clean and if they do get marked, it is their job to go about taking care of that (especially since apparently they gave you a dirty IP range to begin with...). If they are not doing anything about it, find a new provider. Having your IP range flagged as spam is bound to happen eventually, however how the provider reacts to it should be the determining factor.
Honestly at this point I'd just recommend signing up for a new provider :-/