I can only speculate but in other cases this could happen when trying to sent a larger file attachment on a line which is bandwidth constraint.
To debug further go to Administration->Log subscription and create a new log of type "Domain Debug Log". Specify the domain you are having problems with, and make the number of SMTP sessions at least 20. Once you are running in the problem again, download that log and check the content for the following events :
If the log only shows the message headers, and stops at the "data" section, then an MTU problem is the cause, so they might need to fix their firewall to allow ICMP path discovery trough. If you see data transmitted after the header part, then the bandwith is simply too slow.
I hope that helps.
-Marc
