I second using bayes! It works like a charm in most cases.

I host my mail on my personal mailserver and use spamassassin with bayes and network (rbl/checksum) lookups. I'm down to maybe 1 false negative per week.

I've set up exim to use rbls also, which returns a "user not here, go away" result code to the sending mail server that was found in the rbl. With rbl checks, 80% of the spam doesn't even make it to spamassassin. Another 19.9% is easily handled by heuristic checks, checksums and bayes.

I have, however, begun to see attempts to poison the bayes databases by including many random words that aren't typically associated with spam. This is where the heuristics come into play. Usually these emails are a bunch of random words (bayes doesn't think its spam), and a single image, which is an ad. Spamassassin detects most of these, especially when you have the distributed checksum tests like pyzor and dcc turned on.