I finally got around to setting up greylisting on my mail server using postgrey. I first heard about the technique from Filtering Spam with Postfix by Kirk Strauser. The article also talks about enforcing proper use of the HELO command in SMTP. Anyway greylisting causes your mailserver to reject a first attempt at sending mail to you with a 450 response code, which basically means, "I'm busy now, could you come back later?" A second attempt is accepted without question. I'm simplifying a little, but this is essentially how it works. The benefit is that most custom spam server software and worms will not make the second attempt at all. According to the article this cuts out a big chunk of spam.
Probably this will not be a long term solution. Spammers will be more careful about following the SMTP spec if a lot of servers do this kind of thing, but for now it's great. Looking at my own logs it looks like the HELO restrictions are making a bigger impact for me.
If only I could convince my backup MX to do the same thing! My brother was kind enough to serve as my backup MX. He set up a special POP account on his server that will hold any mail it gets for me until I pick it up using fetchmail. Much of my spam comes through my backup MX, which has looser restrictions than mine does. Since fetchmail is all that my machine sees it gets in without question.
Update: It's been a week and I haven't had any spam at all except through my backup MX! The saddest part is that spam levels are back up to where they were before I implemented the restrictions.