You'll get that from any type of hosting though really. I know I had to really fight to get some Verio colo IPs removed from the various lists and even then I wasn't 100% successful. Some of them once you're on the list, you're on there forever stupidly.

What is blacklisted like crazy everywhere are the Amazon EC2 IPs. It seems to be a haven for spammers and attackers. Amazon at one point just terminated that particular instance and let the spammer/attack create more. I'm unsure whether they still follow that policy.