from your logs, my first guess would be a slow internet connection might be causing the trouble.
have you tried to check the servers Internet speed? for example try to ping external addresses like yahoo or hotmail and observer the RTT.
In your case i think your server tries to connect to the external servers receiving mail, but due to the slow connection, its timed out and the foreign server breaks the connection.
Also your delay in the logs is really magnificent, i think you should check the internet speeds of that server first.