S linuxem by to nemelo mit vubec nic spolecneho. Skontroluj spojeni na exchange SMTP z vnitrni site ( napriklad pres telnet port 25, na prikaz "HELO seznam.cz" by mel odpovedet ), a potazmo zacit hledat problem na exchangi pripadne na stavajicim routru.