That's the standard response from gray-hat ISPs who permit spam on their networks.
I know of no blacklists that require money to be delisted. However, ISPs often see "kicking spammers off" as a form of revenue loss, since they are no longer making money from the spammers they boot.
If my ISP said something like that to me, I'd change ISPs. Its an admission that they allow spam.
