Bizarre Exchange issue; cannot send to external addresses, from all but ONE user

I have a small Exchange environment, 10 PCs running Outlook 2007, 3 Droid phones, 2 iPhones and a couple Ipod touches. I came in this morning to the realization that external recipients are not getting mail from us. There are no errors or kickbacks, the mail just disappears. Here's the weird part, the Apple devices connect via EAS, and are able to send no problem, recipient gets the message. The Android devices and all Outlook users (EXCEPT ONE!) are able to send, but the recipient never gets the mail, its like its sent to nowhere. OWA gives the same result as Outlook.

Message tracking in Exchange Console shows the messages going out.

My SMTP logs show exactly the same result for a message that wasn't delivered, as one that was by that one user that is able to send.

All mail to internal users works properly.

EDIT: There is only ONE user that can send, and this is through Outlook or OWA. To clarify,

User1 cannot send with Outlook or OWA, or his Droid using EAS to my gmail address, but can connect his iTouch to EAS and it sends fine.

User2 can send to my gmail account using Outlook, OWA (from any computer) or his iTouch. This is the ONLY user not experiencing any issues

I cannot send to my gmail account using Outlook or OWA, but my iPhone works using EAS

Here is the SMTP log of an undelivered mail:

Tue, 19 Oct 2010 13:40:38 -0400",
EHLO mail.domain.com,

250-cm-omr9 says EHLO to our.external.ip.address:34152,

250-8BITMIME,

250-PIPELINING,

250-AUTH=CRAM-MD5 LOGIN PLAIN,

250-AUTH CRAM-MD5 LOGIN PLAIN,

250 ENHANCEDSTATUSCODES,

AUTH LOGIN,

235 Authed. Go on.,

63,sending message

MAIL FROM:User2@domain.com,

RCPT TO:me@gmail.com,

RCPT TO:User2@gmail.com,

250 MAIL FROM accepted,

250 RCPT TO accepted,

250 RCPT TO accepted,

DATA,

"354 continue. finished with ""\r\n.\r\n""",

250 OK 5C/1B-10393-618DDBC4,

QUIT,

221 cm-omr9 closing connection,

Here is the SMTP log of a delivered mail:

220 cm-omr4 ESMTP ecelerity 2.2.2.41 r(31179/31189) Tue, 19 Oct 2010 13:42:18 -0400",

EHLO mail.domain.com,

250-cm-omr4 says EHLO to mail.domain.com:5524,

250-PIPELINING,

250-ENHANCEDSTATUSCODES,

250-8BITMIME,

250-AUTH=CRAM-MD5 LOGIN PLAIN,

250 AUTH CRAM-MD5 LOGIN PLAIN,

AUTH LOGIN,

235 Authed. Go on.,

65,sending message

MAIL FROM

RCPT TO:me@gmail.com,

250 MAIL FROM accepted,

250 RCPT TO accepted,

DATA,

354 continue. finished with ""\r\n.\r\n""",

250 OK F9/15-07570-A78DDBC4,

QUIT,

221 cm-omr4 closing connection,

.220 cm-omr5 ESMTP ecelerity 2.2.2.41 r(31179/31189)