Ok, this was a really hard one to solve. I tried everything you can think of to get this to work. I found a great manual online, good work to the author here:
I also found some good troubleshooting steps here as well:
However, that still didn't help me, this was an upgrade from 2003 exchange, I modifed the ADSIEDIT stuff, the send/receive connectors, the transport connectors, the global settings, the mailbox settings, etc..etc... I still got the #550 5.3.4 SMTPSEND.OverAdvertisedSize; message size exceeds fixed maximum size ## error.
Now exchange 2007 out of the box has a 10mb email size limit. I could send 13mb attachments, just not 15+. This is odd for several reasons, but let me explain the eventual fix. I was trying to "double" the size to 20mb from 10mb, so I went from 10240 to 20480 in the "size" settings.
We enabled verbose logging on the Edge SMTP machine, it showed the 18mb test email I was sending was actually 25xxx in size, so my 18mb attachment, the "SMTP" size of the email was 25 megs-ish. We increased the sizes up to 30000 and blamo..20mb email attachments now work. I tried sending from gmail and another exchange server, both significantly increased the size of these emails with the 18mb attachment. I'm not sure why, but that is a problem for another day.