When-ever we get a spam, I check the sending IP against an inventory of
all the e-mail we've ever received going back about 6 years.  

More specifically, say the spam came from 1.2.3.4.  I check and see if
we've ever received a valid or "good" e-mail from 1.2.0.0/16.  If not,
then I block 1.2.0.0/16.

We get maybe a dozen spams a week to addresses like "sales@" and
"support@".

Back in 2005 these accounts were getting 50 spams a day - and I would
block 1.2.3.0/24  - but that was useless.

Then in 2006 we changed ISP's and I forgot to enter our MX record - but
I didn't realize it for a few months.  We were still getting mail - but
the spam seemed to have stopped.  I didn't realize that when an MX
lookup fails, that the sending server will resort to the A record, and
that's what was happening.  But spam zombies don't impliment the full
smtp specification, so they didn't do anything when the mx lookup
failed.  That worked well for about 2 years and then some spam started
trickling back in.

I then looked up some IP allocation lists for various countries.

We block all of Russia and Ukraine, all of South and Central America,
most of China (with some exceptions) and most of Africa (except South
Africa).

Our "Contact Us" web-page lists a gmail account (which forwards to our
"sales@" account) that can be used if someone has tried our regular
contact address and gets a "delivery failed" response.  When someone
tells us they've gotten a "delivery failed" or "rejected" response, I'll
go in and adjust the IP-address blocking setting to prevent it from
happening in the future.  I might have to do that once or twice a year.

If I find that a particular domain is used frequently in the "Return
Path" then I can block based on that as well.  I block many "yahoo.x"
domains (where x is .co.uk, .hk, .mx, etc, but not .com or .ca).

Our SMTP software (post.office, made by the defunct software.com) runs
on an NT-4 server and dates to about 1999 or 2001.  It's the most
rock-solid piece of software running on a rock-solid server I've ever
seen.  I basically do nothing to manage it other than adjust the
blocking list and create new accounts, adjust aliases and forwarding,
etc.  And I do all that from a simple web-based management interface.

I only wish it could do more in terms of blocking based on subject line,
user-agent, etc.  It doesn't do any message heuristics (I think blocking
based on that is a crock and a mine-field of trouble).  It can only
block based on IP, and the full or partial address in the Return Path.

It has a limit of 10,000 lines in the IP block-list.  Each line can
contain an individual IP or a subnet.  I've got it filled with about
8,000 entries at the moment.  It doesn't connect to any DNSRBL service
(I probably wouldn't use it even if it did).