I may have said this earlier and I'll say it again - if mail won't send and you know the settings are correct because they match a different server that does work, check local anti-virus settings and talk to the person in charge of the email server security settings.

As you know, trojans taking over servers to send spam is a huge problem, and measures to prevent this may very well interfere with SQL Database mail.