Have you guys considered an automatic system with collateral. I'll gladly sign a contract stating that I will be under X% bounce rate for the next month and put some collateral (depending on the email volume requested). At the end of the month you get your collateral back.

It's a purely economic and automated solution that should work well enough for small operators (collateral for a small email volume should be small since spammers really need high volume)