unstable.nl's anti-spam measures
First of all a lot of spam is caught with some very simple rules in the mail server (Postfix). Eg. mail from/to non-existent domains is rejected. In case you're interested in unstable.nl's mail server configuration, you can have a look.
When the simple checks fail, there are two seperate and distinct anti spam measures that follow at unstable.nl. The first system is policyd-weight. It integrates with Postfix and checks for numerous blacklists and other suspect conditions, and produces a score. This is handy because eg. outright rejecting all DSL IPs would be too harsh (heck, the server is on DSL itself), but on the other hand it is a good prediction of spam, so it should count in the score.
The second is the popular SpamAssassin, which combines many approaches into one scoring system.
I've set up a kind of spam-trap which receives e-mail to be added to the spam database. In fact I just watched which non-existing addresses were getting mail and I added aliases for those addresses to the spam-trap. Also the IP address of the sender gets blacklisted using relaydb.