It's specific to the outlook.com account using the outlook connector, but only specific to machines inside their network.
hashbrown: DNS perhaps? Maybe try hard coding DNS on those machines to bypass modem, or test Google DNS.
I may send a short text email with 5x 500kb jpgs attached. The email will say it failed, but may in fact have sent, but only 2 of those 5 attachments are sent.
Or, I may send a text email with a 1.5mb PDF attached. Again, it will say it failed, but sometimes the text is received, but not the attachment.