Double check that you are using the correct SMTP server for your domain, If you are unsure, contact the host.
If you have the correct SMTP server, here are some additional things to check:
1) Make sure the from address is a valid address for your domain.
2) On the mail settings tab, check the option to include the from address as an additional parameter.
if you are still having problems, you should contact the host to have them look into the SMTP server error logs to see why the SMTP server is not relaying the email.