We also run a challenge/response-based anti-spam system, and have faced similar blacklisting to what you're describing by spamcop.net.

We usea lot of intelligence on our verification process to make sure we challenge as little forged mail as possible, using ideas that you mention in your c/r best practices document, as well as SPF, anti-virus, and other heuristics.

Because our system does not always operate on the receiving smtp server (we poll some mail via pop/imap/etc), any responses to forged emails are considered backscatter. This is one of the things we strive to minimize.

We also run all of our challenges out through a single IP address, so just in case that host does get blacklisted, the rest of our customers' outgoing email is not affected.

The blacklist that has given us the most grief is SORBS. About a year ago, our entire netblock was blacklisted by them. After much effort, we were able to have them only block the single IP used by the challenge process. While that is certainly not what we wanted, that was as far as we could get with them.

However, just recently, they decided to block our entire netblock again. Why? They had not seen ANY problems with the rest of the IPs, which all require authentication, and have rate-limiting and other abuse-controls, but they felt that we hadn't done enough to "fix" our system, and wanted to exert pressure on us to do that.

What good did this do? Well, we spent a lot of time trying to convince them what a bad idea it was.. A lot of time explaining to our users why they couldn't send emails to their friends and family whose ISPs use the SPEWS list.. And a lot of time talking to ISPs, who certainly weren't expecting/intending to be blocking legitimate email by using their blacklist.

Ultimately, we were able to come to an agreement where they went back to just blocking our challenge ip again. But I have no doubt it will happen again, with spews or with someone else. Sure we can play cat and mouse, jump around various ips, etc. But that's not what we're interested in.

When we're blacklisted, we do exactly what you did: make sure everyone involved knows exactly what happened and why, and let the blocking mail provider, and the recipient who didn't get the email, decide whether using that blacklist is really in their best interest.

Daryn
Spam Arrest