As by now most spam probably originate from hijacked nodes or dedicated spamming networks, it is questionable whether blocking open relays is an effective tool against spam right now.

On the other hand, the blacklists of the IT magazine iX prove to be very effective: They have a nearly real-time IP blacklist of servers, that sent verified spam during the last 3 days (only), combined with fuzzy text signatures of spam mails, all available via DNS zone ix.dnsbl.manitu.net or downloadable lists (delayed by about 20mins).

Here, even their DNS based blacklist alone blocks most of incoming spam, with an extremely low rate of false positives and complains: They claim to have about one removal request in about 6000 new entries, where the blacklisting usually originated from infections.

Their fuzzy checksum techniques help avoid costly text analysis and is based on simple text manipulation, notably one of their strongest techniques is to fingerprint the distribution of whitespace as layed out in this optimized procmail script.

Spam infrastructure isn't unlimited - but blacklists have to be very large or really fast.