Relay Denied errors more abundant lately.

I've been seeing an increased number of "Relaying denied" NDR's coming into my mail server these past week weeks.  I've checked and double checked with my ISP to ensure my DNS records are configured properly and they swear up and down they are.  I have been questioning them about Reverse DNS and they tell me they "have many customers using mail servers that are set up the same way we are"...

Most of our mail is fine, but maybe 1-2% of it comes back with a relay denied NDR of some sort.. usually stating "Authenitcation" issues.  Our setup uses Exchange 2003 and local Outlook 2003 from our office where the mail server is located.

Here's an example from my log files; can anyone make sense if it?

207.38.29.36, OutboundConnectionResponse, 10/25/2007, 11:58:59, SMTPSVC1, SERVER, -, 297, 0, 78, 0, 0, -, -, 220 ns3.quik.com ESMTP Sendmail 8.13.1/8.13.1; Thu, 25 Oct 2007 12:00:01 -0700,
207.38.29.36, OutboundConnectionCommand, 10/25/2007, 11:58:59, SMTPSVC1, SERVER, -, 297, 0, 4, 0, 0, EHLO, -, server.tacs.org,
207.38.29.36, OutboundConnectionResponse, 10/25/2007, 11:58:59, SMTPSVC1, SERVER, -, 375, 0, 92, 0, 0, -, -, 250-ns3.quik.com Hello 69-30-69-184.dq1mn.easystreet.com [69.30.69.184], pleased to meet you,
207.38.29.36, OutboundConnectionCommand, 10/25/2007, 11:58:59, SMTPSVC1, SERVER, -, 375, 0, 4, 0, 0, MAIL, -, FROM:<USER@tacs.org>,
207.38.29.36, OutboundConnectionResponse, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2563, 0, 38, 0, 0, -, -, 250 2.1.0 <USER@tacs.org>... Sender ok,
207.38.29.36, OutboundConnectionCommand, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2563, 0, 4, 0, 0, RCPT, -, TO:<USER@speedpal.com> NOTIFY=NEVER,
207.38.29.36, OutboundConnectionResponse, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2657, 0, 84, 0, 0, -, -, 550 5.7.1 <USER@speedpal.com>... Relaying denied. Proper authentication required.,
207.38.29.36, OutboundConnectionCommand, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2657, 0, 4, 0, 0, RSET, -, -,
207.38.29.36, OutboundConnectionResponse, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2719, 0, 21, 0, 0, -, -, 250 2.0.0 Reset state,
207.38.29.36, OutboundConnectionCommand, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2719, 0, 4, 0, 0, QUIT, -, -,
207.38.29.36, OutboundConnectionResponse, 10/25/2007, 11:59:02, SMTPSVC1, SERVER, -, 2797, 0, 41, 0, 0, -, -, 221 2.0.0 ns3.quik.com closing connection,Start Free Trial