If you are sure that authentication works as expected while inside your network, chances are it is a firewall issue.
A common problem is Cisco’s MailGuard function found in their firewalls. When enabled, this will reduce the allowed SMTP commands the firewall will let through. Among them “AUTH”, which is needed to authenticate.
If you manage your own Cisco PIX firewall, make sure you disable MailGuard by issuing the following command in your firewall:
no fixup protocol smtp 25
Alternatively, ask your ISP to do this for you.