If you receive this error and have exhausted all other recommended options from Microsoft and other sources on the web then you might have stumbled upon the same unknown exchange feature/bug that we suffered from.

After doing some digging around it seemed that when we installed exchange it did not set permissions properly on some of the existing users. So some users could not authenticate against the SMTP server even though it seemed like they had the exact same permissions and SMTP settings as other users that could authenticate.

To solve the problem we had to create new user accounts. New user accounts did not receive the same SMTP error.

To test if you suffer from the same problem just try to create a new domain user account and assign an exchange profile/email address to it. If this user is able to authenticate through SMTP then you found your culprit.