Have you setup an SMTP server? When setting up Outlook your e-mail provider may have given you your POP3 address (mail.domian.com) for retreaving e-mails, but if you havent setup your SMTP server (smtp.domain.com) then you can't send e-mails.
Is this the problem?
Is this the problem?