Hm, greifst du vom gleichen Rechner aus mal mit Windows und mal mit Linux auf Exchange zu?
Eventuell muss dein Rechner auch erstmal freigeschalten werden damit das klappt.
SMTPS kann das Mail::Sender nicht, wenn ich die Doku richtig lese. Allerdings kann es mit SMTPAUTH umgehen. Duerfte in deinem Fall aber nicht der Knackpunkt sein.

Wie isses denn mit dem telnet-Kommando? Kriegst du da ueberhaupt nen Connect zum Exchange-Server?