My company has had multiple Outlook syncs on for quite awhile, and they are getting login prompts from the machine name instead of the internet.domain.com address, like they should. I haven't changed the alternate access mappings, nor has anyone changed their passwords. Trouble is, logging onto the machine name is prompting, but your correct password won't make it go away. Also, reconnecting won't fix the issue.
I found out that I accidently put Negotiate in the Windows Authentication first, then NTLM. I deleted the Negotiate in IIS Manager and everything is working correctly.