OT: How do other ISPs deal with SORBS?

Ok, I know this isn't a Postfix question, but there are a lot of mail
admins here and I'm after suggestions/opinions, so...

We have a bunch of customer mail relays. A while back, one of our
lovely Windows-using customers managed to leave their computer open to
abuse and since they relayed through us, we got the blame. As usual
with this sort of thing, once it was spotted their access was closed
down until they had fixed the problem and everything went back to
normal. Almost. Sometime during this incident a single message made
its way into one of the SORBS spamtraps, so they now believe that we are
a junk mail organisation (an interesting assumption based on one
message, but that's another issue.)

The web site basically says "send us money and we might remove you".
All well and good, but given the volume of mail that goes out of a
typical ISPs mail system there are always going to be some that go
astray (especially given the number of Windows viruses doing the rounds
right now) and if it only takes a single message to get listed this
could get very expensive.

I'm sure others here must have had similar experiences. How did you
deal with it?

Chris.