Some destination email servers report that my sendmail app is relaying when it isn't.  Possible configuration problem?

We currently send email from a webapp via sendmail.  The emails are sent directly from the server, and do not go through a smart host.  

Many messages bounceback with one of two distinct errors: 5.7.1 or 4.7.1.  The bounceback error messages either seem to indicate that they think the message is being relayed through localhost or that we're connecting in some strange fashion.  

Here's one example of an error:

You do not have permission to send to this recipient. For assistance, contact your system administrator.
< [sendmailserver].[mydomain].[com] #5.7.1 SMTP; 550 5.7.1 ... Relaying denied>

Could not deliver the message in the time limit specified.  Please retry or contact your administrator. < web2 #4.4.7>  

The message reached the recipient's e-mail system, but delivery was refused.  Attempt to resend the message.  If it still fails, contact your system administrator.  < web2 #5.2.0 SMTP; 550 5.7.1 Unable to relay for [externaladdy@domain.com]>

(The strange thing on the last 2 errors is that web2 is the machine name of the sendmail server.)

Then there's this error:
The original message was received at Thu, 20 Mar 2008 12:46:53 -0400 from localhost.localdomain [127.0.0.1]


Mail from a separate Exchange server do not bounceback when sent to the same addresses.  I sent a test message from both servers (sendmail and Exchange) to a gmail address and here is the only differences in the headers:

From Exchange:
 Received: from [exchgsvrname].[mydomain].com ([exchgsvrname].[mydomain].com [Exchserver external IP])
        by mx.google.com with ESMTP id o27si4024191ele.8.2008.03.20.12.54.14;
        Thu, 20 Mar 2008 12:54:15 -0700 (PDT)

From Sendmail
Received: from [sendmailsvrname].[mydomain].com ([sendmailsvrname].[mydomain].com [Sendmail ext IP])
        by mx.google.com with ESMTP id p60si232969hsa.1.2008.03.20.12.56.18;
        Thu, 20 Mar 2008 12:56:22 -0700 (PDT)
Received: from web2 (localhost.localdomain [127.0.0.1])
     by [sendmailsvrname].[mydomain].com (8.12.8/8.12.8) with ESMTP id m2KK7DA9013143
     for <mygmailaddy@gmail.com>; Thu, 20 Mar 2008 16:07:13 -04003

It seems that some receiving servers are seeing the 2nd "Received" section and assuming we're relaying.  The error that says it won't accept mail from localhost.localdomain is particularly confusing.   On a test sendmail server I tried various combinations of masquerading and using genericstable to mask my login name, but I was never successful in removing the second "received from" section or get rid of the "localhost" designation.  Can you offer any advice on if this is a problem on my end?  Is it fixable? Thanks for the help.