Well I don't know anything about your company's mail server but to venture a guess: Perhaps your company's mail server requires SMTP authentication before relaying mail for another server?