Many servers these days require authentication for sending mail and by default, most clients set this to "not needed"... Verify the setting... Also, try to contact the service provider for help, they will be best able to sort it out... Just go through their faq before that...
Arun