I'm confused. Who are you billing and for what services?
Let's say our direct customer is CustomerA. They seem to buy rackspace from BusinessB. CustomerA seem to retain BusinessC for "IT Solutions" even though all three entities purport to be IT solutions providers. BusinessC came into the picture after the spamming started saying a wholly different /24 (Different from the spam source) "doesn't work". It routes fine on our end. I have a feeling they've been added to some RBLs but I haven't found them listed yet. Just a simple ethernet handoff in a colo. We delegated rDNS to the servers of their choice and haven't heard a peep out of them until now.
Spamhaus is the first one that comes to mind. From what I understand of your description, this doesn't sound all that different from typical spammer behavior. Multiple layers of indirection seems to be the latest thing for spammers.
---------------------------------------------------------------------- Jon Lewis | I route Senior Network Engineer | therefore you are Atlantic Net | _________ http://www.lewis.org/~jlewis/pgp<http://www.lewis.org/%7Ejlewis/pgp>for PGP public key_________