I dont think that is a problem from the server as others are happy with working smtp.
Can we debug!!
Please try reconfiguring afresh.
Send email to different clients -gmail,yahoo,msn etc.,
It should go.
Also configure this one differently i.e., previously it was emai
Revert back