A few questions.
1) Does the message itself go through each time? Do they receive the message but minus the attachment?
2) Do you get a bounce of any kind?
3) Are you using our server for outgoing mail?
4) If you use a different mail client, do you experience the same problem?
We don't allow messages larger than 40 Mb, but you should be well within those limits. I think it's fairly unlikely that the problem is with our mail server itself, although it's certainly possible.
If they're receiving the message but not the attachment, it would be great if you could get me a copy of the entire message they receive as an rfc822 attachment.