It sounds like your hosting company is prohibiting you from sending mail. Most hosting firms do this and require that you use their mail relay for sending instead of allowing you to send directly. This is to prevent abuse. You probably need to investigate what they need you to do in order to allow you to use their mail relay, and get the settings to allow you to connect to it. This is a common problem and you can find other cases like it in this forum.