The problem is that email orginating on my machine is from
localhost.localdomain, and not example.com (as it should be since
we'll assume for this document that my host is example.com).

Notice that the ctladdr and the from both say
localhost.localdomain. The mail bounces from the recipient's host.

Dec  8 09:32:34 example sendmail[4024]: iB6Jeqrn030992: to=<mst3k@someotherdomain.com>, ctladdr=<mst3k@localhost.localdomain> (501/501)
, delay=1+18:51:42, xdelay=00:00:00, mailer=esmtp, pri=3900538, relay=mail.someotherdomain.com. [128.143.2.9], dsn=4.2.0, stat=Defer
red: 450 <mst3k@localhost.localdomain>: Sender address rejected: Domain not found


Dec  8 09:55:55 example sendmail[4083]: iB8EttLe004083: from=<mst3k@localhost.localdomain>, size=331, class=0, nrcpts=1, msgid=<
200412081455.iB8EttCd004080@localhost.localdomain>, proto=ESMTP, daemon=MTA, relay=localhost.localdomain [127.0.0.1]

The problem was that example.com was in /etc/hosts incorrectly.

The wrong entry:

127.0.0.1       localhost.localdomain   localhost example.com	example

The correct entries:

127.0.0.1       localhost.localdomain   localhost example.com
192.0.34.166	example.com example