Hmmm...checking server requires authentication should fix this. There are services such as http://www.smtp.com/
that may fix this for you if nothing else does. It's fee based but it isn't to costly. Maybe try it for a short time to see if it works. It will at least get you up and going, and in the meantime you may find a fix for the problem.