Have you tried contacting management or calling them?
The host should take full responsibility for their IPs and do what needs to be done to get them un-blacklisted. I'm not familiar with VPSville but they may come on here and try to clear things up with you.