When Microsoft Exchange sends an e-mail, the message size may change due to the encoding used to package it. Messages with attachments can expand even more, since the only way to send e-mail attachments is to convert them from plain ASCII to MIME or UU-encode the message. Even if an attachment is smaller than the limits set in Exchange, it may not be accepted because its MIME-encoded or UU-encoded size is too big. This happens most often when limits are set for inbound SMTP mail. An incoming MIME-encoded e-mail with attachments can increase in size anywhere from 30% to 40%, depending on how many separate attachments, line breaks, MIME headers or other non-data elements are in the message. The exact size can vary enormously, especially since mail systems all behave a little differently when converting e-mail and attachments to MIME. The same problem exists in reverse, where messages sent from your domain will be constrained by message limit sizes on other hosts. Likewise, mail sent from your domain is going to expand anywhere from 30% to 40% in size when converted. [more]
A third-party program, such as UUDeview (http://www.miken.com/uud/), can help you find out just how much larger a MIME or UU-encoded version of a given file will be. (Note that this tool does not calculate things like message size overhead, but it can still be helpful.) The exact maximum incoming and outgoing message size is going to be up to the e-mail administrator, but should be set with these caveats in mind.
Also, take the time to explain to users that when they send attachments, they need to be mindful that messages will increase in size.