Who is your host? What are the email settings they recommend? What are all of the settings you have in Admin> Configuration> Email Settings?