DNS, Mail trouble

[Jason McGraw]

Some of our users are having trouble sending mail to particular domains.
These are examples of the messages in the maillog:

Aug  9 09:39:21 explorer sendmail[6330]: f79EDZD03091:
to=<Kaiser_Tom_J at cat.com>, ctladdr=<gjohnson@
boyertrucks.com> (559/45), delay=00:25:46, xdelay=00:00:11, mailer=esmtp,
pri=147764, relay=mail2.ca
t.com. [198.206.246.199], dsn=4.0.0, stat=Deferred: 451 4.1.8
<gjohnson at boyertrucks.com>... Domain o
f sender address gjohnson at boyertrucks.com does not resolve

Aug  9 09:39:40 explorer sendmail[6330]: f78FubD17411:
to=<christopher.aguilera at yokota.af.mil>, ctla
ddr=<dnewville at boyertrucks.com> (586/45), delay=22:43:02, xdelay=00:00:03,
mailer=esmtp, pri=2100719
, relay=yok-sr2.yokota.af.mil. [131.36.116.57], dsn=4.0.0, stat=Deferred:
451 4.1.8 <dnewville at boyer
trucks.com>... Domain of sender address dnewville at boyertrucks.com does not
resolve

Most mail goes through just fine. I assume it has to do with DNS, but I am
new to this and I'm having trouble finding a low level answer to this
question.

Could anybody help out?

Thanks,

Jason McGraw