I'm 99% sure I found the problem with New Outlook not connecting to IMAP account on Smartermail.
If the user's email address was used to create a Personal Microsoft Account previously, that causes the issue. The way I tested it is I have a domain with three users. Only one of those users could not connect. When I renamed his email address, it worked right away.
The two accounts that had no problem both never had a Personal Microsoft Account (MSA).
The solution is to rename the problem user's email address, and then create an alias pointing back to his new email address (which essentially would just used for login going forward). Then just change the default From address so they are always sending from the alias in webmail.
What I'm not entirely sure of is where the MSA might have been originally created. Could be Skype, XBox, Windows Live, MSA or a Windows Login. But, who cares I guess at this point.
WTF, Microsoft!?!?!