Why do some servers refuse SMTP connections from my Linux box, but accept connections from hosts running other operating systems?

If you are sure this isn't a policy issue (that is, your box isn't administratively blocked for some reason), this may be because your Linux box has ECN (Explicit Congestion Notification) enabled in its TCP/IP stack. There are many broken firewalls that refuse connections from ECN-enabled hosts. You can check the state of your box by running

cat /proc/sys/net/ipv4/tcp_ecn

If the value is "1", you have ECN enabled. You can turn it off by running this command:

echo "0" > /proc/sys/net/ipv4/tcp_ecn