Even if your external Exchange Autodiscover service is configured correctly you may still have issues with rejected login credentials if your internal and SMTP domains are different. Lets say your internal Active Directory domain is mydomain.local, but your external SMTP domain is mydomain.com and user’s have emails in format name@mydomain.com.

In this case Autodiscover service will submit username name@mydomain.com, but it will be rejected by your Exchange server as actual User Principal Name (UPN) within the Active Directory is name@mydomain.local.

Obviously users can manually enter their UPN during email account setup, but this somewhat defeats whole purpose of Exchange Autodiscover setup where end users can configure their email accounts by simply providing their email address and password.

To work around the issue you can use UPN Suffixes feature within Active Directory:

• Open Active Directory Domains and Trusts, click Action > Properties and add your SMTP domain(s) as Alternative UPN suffixes.
  
• Open Active Directory Users and Computers > User > Properties > Account.
  Click on the drop down next to User logon name and change it to match user’s primary external SMTP domain.
• Repeat for other users.

Be aware that this changes default user login suffix not only for Exchange Autodiscover, but globally across Active Directory. Normally this is not a problem, but something to be aware of.

MS Server 2008 R2
MS Exchange 2010