Reducing the amount of challenges is probably the right move to take. You can reduce the likelihood of banishment in this way, as well as become less of a nuisance to the Net. In other words, try ruling out cases when messsages are rather obvious spam. It leads to lower volume of messages being dispatched, which in turn can avoid blacklisting.

I use SpamAssasin, which is active at a layer higher than challenge/response (in this case Apache with BoxTrapper). Whatever gets scored as spam will be put aside in a mail folder which is reserved for spam. Only messages not marked as spam (and not in the whitelist either) will have a challenge delivered. This cuts down the number challenges by about 70% in my case. It never entails any false positive because I set the thresholds high.