Email from IOS with attachments larger than 7.5Mb gets stuck in outbox and constantly tries to resend. Costs us hundreds in data fees

We have an on premise Exchange 2013 server. When sending email with large attachments from ActiveSync accounts on IOS devices, the email gets stuck in the outbox and won't send. It keeps trying to resend and can cause our users to blow their data allowance and start costing hundreds in data fees. It does not do this when sending from a Gmail account linked on the phone, or from a windows 8 phone.

I've narrowed down an attachment size of about 7660870 bytes before the issue starts occurring. For a few bytes over this limit, the email will have a failure message, but will still be sent through without the attachment. If you add a few more bytes on, we get the failure message but no email goes through and it gets stuck in the outbox. These sizes are under our allowed size limits for internal and external mail. Additionally, I'm guessing the behavior of this issue depends on the total size of the message including header, body, etc., not just the attachments.

Has anyone seen this happen before, or have any idea what could be causing this?

Take a look at https://technet.microsoft.com/en-gb/library/hh529949(v=exchg.150).aspx

There is an interesting line at the bottom of that page that implies the effective maximum limit is about 33% less then the limit you have configured. Given the default for active sync is 10mb and you are seeing problems around 7, that would make sense.

Try increasing to 20mb and see if that makes a difference.