[BlueOnyx:05512] Email question

[Gregg]

I have something weird happening from time to time.
A client gets a return message saying that the email did not go through,
because of reverse entry.
The original message was received at Fri, 1 Oct 2010 13:44:36 -0700
from localhost [127.0.0.1]
   (reason: 554 "Refused. You have no reverse DNS entry.

However, the reverse is set properly, otherwise we would be getting a lot
more bounced messages.
I went through the log and found this:
Oct  1 13:44:35 ns1 sendmail[31500]: AUTH=server, relay=localhost
[127.0.0.1], authid=username, mech=PLAIN, bits=0
Oct  1 13:44:36 ns1 sendmail[31500]: o91KiZGc031500:
from=<username at sendingdomain.com>, size=1020, class=0, nrcpts=2,
msgid=<4D13FE73-0581-44F3-B5DD-A7D6B50149B5 at receivingdomain.com>, proto=ESM
TP, daemon=MTA, relay=localhost [127.0.0.1]

Then further along, I get the return message:

Oct  1 13:44:53 ns1 sendmail[31502]: STARTTLS=client,
relay=receivingdomain.com., version=TLSv1/SSLv3, verify=FAIL,
cipher=AES256-SHA, bits=256/256
Oct  1 13:44:54 ns1 sendmail[31502]: o91KiZGc031500:
to=<customer.service at receivingdomain.com>,
ctladdr=<username at sendingdomain.com> (707/539), delay=00:00:18,
xdelay=00:00:18, mailer=esmt
p, pri=151020, relay=receivingdomain.com. [their IP address], dsn=5.0.0,
stat=Service unavailable

My first thought is, why would the AUTH=server be using localhost as relay
and not the main server IP address?  I think that is the problem, the
receiving server somehow thinks that it was sent by 127.0.0.1?

Send, why is the auth=server even coming up? A lot of the users send emails
through the server on a daily basis, and there are very few "AUTH=SERVER"
messages.

Any thoughts? 
Thanks.