Does the outgoing mail server require authentication? Are you using the right outgoing port? Check with your email provider for the correct email settings.
Who is your ISP? They may have an outgoing relay that will work for you too. If you have SPF settings be sure to include you ISP if you choose to use them for sending email.