I've run into this issue several times at various clients and it invariably ends up being either sales or marketing people trying to send out promo PDFs, etc. to a distribution list of prospects or customers.
When I explain to them that large attachments are no good for us or the client, as the likely can't receive large attachments anyways, or they're spam filtering will likely quarantine it*, they're very receptive to hearing about a better way to do it.
What's worked great in the past was to either train them on using a file drop service (like http://drop.io) or setup an FTP drop (usually on their website) and delegate a member of their team to upload files and give them a link to use. This works very well: they like the fact that they can also track metrics if their site is setup this way (or you can elevate yourself to Hero Status with 15 minutes of your time setting up Google Analytics on the website).
Another option might be to offload these emails to a dedicated marketing email service like ConstantContact. It's very user-friendly, allows them to track click-thrus, manage (import/export) a distribution list, WYSIWYG editor with templates, etc. and fairly inexpensive.
If none of this will fly, I would recommend setting up message size limits in Exchange. If they're sending to the same recipient domains all the time you can create a separate Send Connector with a more restrictive set of limitations on message size than the others in your organization.
*Slightly embellishing the issue, but hey, it's for their own good. :)