They've been on Outlook.com for maybe close to a year now, but are having issues sending emails with attachments. Whenever they try and send an email with anything but the smallest attachment, Outlook reports the following error:

The weird thing tho, is that the email usually does send, often with some of the attachments (if small). Outlook will continue indefinitely to resend the email until it's deleted from the Outbox, so the recipient gets a number of copies of the email with no or partial attachments.
I've been trying to work out what is causing the problem, and basically have it down to either the modem/router or the ISP. If I setup the account on another PC on the same network, same error. If I setup the account on a PC off their network, it works fine. Even if I setup a brand new user account in the domain management console thing, once setup in Outlook inside their network, the attachment problem appears.
It's seems like something is interrupting the connecting while the mail is sending, but I cannot this/work out what. They have no other issues with their internet connection.
Anyone have any ideas why this might be happening, or what might be done to fix it?