I have Sendmail 8.12 and we notice in our log files that spammers
attempt to send emails to hundreds of invalid email addresses in an
effort to find valid addresses we are using.  They're typically
successful at this and we've received spam on accounts as soon as 20
minutes after they're created.

My question, how can I configure sendmail to prevent spammers from
'scanning' for valid email addresses like this?

Hello again Davious,

For your specific request (slow down spammers) try what's recommended in
  http://www.dshield.org/pipermail/list/2003-October/026939.php
(scroll down a ways for the define commands)
There is also a "tweaking document" that describe these commands (and
a LOT of others) in more detail at
  http://www.sendmail.org/m4/tweaking_config.html

Beyond that, let me describe several alternative approaches that
should slow down (or stop) the spammers from filling your inboxes.
These first references describe an older version of sendmail (8.8 and
8.9) but should still work [unless I describe differently below] in
the newer version.

Let's start with the source - the main sendmail site at
  http://www.sendmail.org/antispam.html
which has a number of good recommendations. Using the first reference
as an example at
  http://www.sendmail.org/m4/anti_spam.html
there are a number of good recommendations that can be summarized as:
 - Relaying is denied by default; if you turn it on, make sure it is
configured properly so you don't become a spammer.
 - Better checking on sender information such as a reverse DNS lookup.
 - Access database. This describes how to set up reject / accept
lists, use the real time blackhole list,
 - Header checks. Some advanced checks based on how the headers are
constructed w/ a reference to digitalanswers for examples (though that
site appears dead).

Also check out
  http://www.sendmail.org/~ca/email/chk-810.html
which describes the differences in sendmail 8.10 and 8.11. [Exceptions noted here]

Of course, sendmail (the company) would like you to purchase MAS which
includes address harvesting prevention:
  http://www.sendmail.com/products/msmgr_antispam.shtml

Another commercial product at Roaring Penguin with MIMEDefang
  http://www.roaringpenguin.com/products/mimedefang/

If you need samples of known spam to help feed some of the tools, try
a spam trap or poison a spammers address harvesting with something
like
  http://www.monkeys.com/wpoison/

An interesting series of messages starting at
  http://lists.roaringpenguin.com/pipermail/mimedefang/2003-May/014568.html
one person's attempt to harvest sources of spam to help seed the
databases. [just use Next message several times to walk through the
analysis / feedback] The idea is to allow some success to spammers
using unused (but likely addresses) and then block them off.

Something called Spamilter which is a module you can add to sendmail
to process your spam more effectively:
  http://www.wanlink.com/spamilter/docs.php

You can also try Sender Policy Framework which can be used to reject
email from other than "authorized senders"; not all sites support this
but its use is growing.
  http://spf.pobox.com/
The downloads page has libspf which describes how to integrate with
sendmail (or use w/ Spamilter). There is also a perl script at
  http://spf.pobox.com/sendmail-milter-spf-1.40.pl
as well.

More links that you can possibly follow at:
  http://www.sendmail.org/~ca/email/spam.html

Search phrases used to find the information includes:
  sendmail spam
  sendmail antispam
  sendmail 8.12 spam
  sendmail address harvesting
  sendmail tarpit
  sendmail address harvesting
  sendmail dictionary attach

Good luck and hope you keep your email clean.
  --Maniac