Proxies or VPNs?
I've found several VPN providers who agree to sell you a private dedicated IP Range, but somehow forget to tell you that it has been previously used for whatever purposes.
Those purposes could perfectly have gotten that range included in one of many blacklists available for everybody. And, even though that IP wouldn't be used by, or available to, anybody else at the same time (hence being private and dedicated) it is not a whitelist IP.
Ask for a NEW Ip to your provider. If they can't or refuse, gladly thank them for their services and stop using them. And make sure to express, when contacting a new provider, that you want IP's that have never been previously used. Many will refuse, but after a while, when they see you aren't going to buy their crap, they'll agree to your conditions.
Of course, after getting your new Ip-or IP range, test them in a blacklist database check. If they show there....they are trying to fool you.
This is just the first one showing up on google:
Blacklist Check
Hope you find this useful.