Msg Size greater than allowed by Remote Host

I'm having an issue sending attachments from our site to external sites via Exchange 2003.

One of our executives recently told me he's trying to send an email that's just barely over the 10MB send/receive limit.  To fix the problem, I allowed his account to send emails up to 15MB in size, but he still wasn't able to.  So I reset his limit back to the store default, and changed the default level up to 15MB.  Still no luck.  The message he got back read, "Your message did not reach some or all of the intended recipients."  It goes on to say, "This message is larger than the current system limit or the recipient's mailbox is full."  At the end of it all, it says, "Msg Size greater than allowed by Remote Host."

The person on the other end says he can receive attachments of any size.  But to test this, I sent an email to my gmail account with a 12MB attachment.  As soon as it left my inbox, I got a reply back with the same Delivery Status Notification (Failure) message our executive was seeing.  According to gmail, they can accept emails up to 20MB in size.  Interestingly enough, I can send that same 12MB file between Exchange 2003 servers on our internal network.  Sending these emails externally results in a bounceback at the same time it gets sent.

So right now, in Message Delivery properties, there's no send/receive limit.  On the SMTP connector, there's no limit set.  On the SonicWall firewally, I don't see anything that would prevent me from sending off larger SMTP messages.  And it definitely doesn't appear to be on the other end.

So my question is, is there something I've overlooked in Exchange or Outlook that would cause this to not be sent?  Is anyone familiar with SonicWall, and know if there's somewhere on there I might look?  I restarted the SMTP and Information Store on the second Exchange server (not fully in production), but it still bounced back.

Any information anyone has would be greatly appreciated.  Thanks!