Additionally we're using the Teergrube to prevent known SPAMmers from inserting their SPAM into our system. We're maintaining a special configuration file for it containing all spammers and open relays we have detected and who haven't been helpful in fixing the problem.
Please also find communication with regard to SPAM at the archive.
We use a mechanism which is called Teergrube (tar-pit). It holds the smtp connection for a specified amount of time or until the spammer gives up. This way the limited resource of open smtp connections at the spammer's site gets filled up and he's not able to deliver his spam. You'll find the source and configuration here. Additionally we maintain a local list of bad sites and use the blocking rules from Debian.
Check if your host is teergrubed.