I use Windows Server 2012 for hosting for a long time and it just stop working after a more than years without any problem. My solution was to add public IP address of the server to list of relays and enabled Windows Integrated Authentication.
I just made two changes and I don't which help.
Go to IIS 6 Manager
Select properties of SMTP server
On tab Access, select Relays
Add your public IP address
Close the dialog and on the same tab click to Authentication button.
Add Integrated Windows Authentication
Maybe some step is not needed, but it works.