"Wrote sternly worded letters to their upstream provider (and their provider's backbone provider)"
Nice of you to hide behind an AC banner. Too chicken to stand up and identify yourself?
Spamhaus only list /24s when the providers don't remove spammers after being given LOTS of warnings.
In any case, your "right" to send mail ends at MY mailserver. I can tell you to fuck off at any time I choose to see fit, for any reason I see fit. If you're in a netblock with a spammer then the outfit you need to beat up on is the wankfest who tolerates having the spammer in their network in the first place.
I'd love it if someone at the reg outed your posting IP - you'd find out what blacklisting REALLY means, as the shutters go down on thousands of individual lists you'd never find yourself removed from.