Depending on your architecture, check your Exchange configuration 

Run the following command on Exchange PowerShell against an account and test sending attachments

Set-Mailbox -Identity "Sebastian" -MaxSendSize 25mb -MaxReceiveSize 35mb

I use UAG with SEG Role in it so I don't have any issues sending larger emails, but maybe the scenario 3 might help? 

Unable to send attachments larger than 10MB (50101175) (vmware.com)

Also, do you receive bounce messages when sending emails out? because you must take into consideration the other end and what's the maxim size they accept, otherwise you will get bounced back.