A fairly common issue on the Internet is that some routers can’t handle window scaling.
This will might give some odd messages to email servers (such as not being able to send mails over a certain size to one receiving mail server)
On option is to turn off window scaling by editing sysctl.conf and adding the following lines
# Uncomment to turn off window scaling (most usefull for linux MTA) net.ipv4.tcp_window_scaling = 0
A warning about doing this; In the long run throughput will not be optimal on this server, but sending mails should work better (so best used on a dedicated mail server).