Maybe you have to authenticate with the mail server before it accepts messages to addresses outside the company. Have a look at your email client's settings and see the $mail{auth} option of Mail::Sendmail.