Outlook 2016 365 Setup/General Issues

There is no official report on this issue, but we have seen an increase in reports of users experiencing, but not limited to, the following problems:
- "Cannot start Microsoft Office Outlook. Cannot open the Outlook Window"
 - "Your mailbox has been temporarily moved to Microsoft Exchange server"
 - Bounce Messages received and showing sent out as outlook_******@outlook.com
 - Users who have Full Access to other mailboxes getting password prompts.
 - Autodiscover resolves to https://Outlook.office365.com/autodiscover/autodiscover.xml first

In these cases, Outlook is attempting to redirect to Microsoft's own 365 and live.com servers if the user's business email address is associated to a Windows Account. That is why to correct this, we advise to have the user remove the business email address from logging into the associated Windows account (such as hotmail, live.com, outlook.com) and remove their business account.
How do I verify if the email address is associated with a Microsoft account?
To verify if this could be affecting your email account, navigate to https://login.live.com/ type in the malfunctioning email address and click next. If you receive the warning stating, "That Microsoft account doesn't exist. Enter a different account or get a new one", then the email address is not associated to a windows account. If you are prompted to enter your password, this means that your email address is set as the primary alias for your Microsoft account and you need to follow these instructions to remedy the issue. 
1. Sign in to (https://login.live.com/) your Microsoft account.
- If the user is uncertain of their Microsoft Account password (not their business email password) use the forgot password option listed on the sign in page.
2. Select “Your info” from the ribbon near the upper left-hand corner of the page.
3. Select "Manage your sign-in email or phone number".
4. You may be asked to verify your identity by email or text. Select the preferred method and proceed with verification.
5. Locate the affected email address under the Account alias section.
6. If the affected email address is the only one listed, select “Add email” and proceed with adding a personal email address so that you can still sign in to your Microsoft account later if needed.
7. Once you have added a personal email address to the account, select Make primary to set it as your primary alias.
- You will be asked to verify ownership of the new alias. Proceed with sending the address ownership verification email.
8.  Once you have successfully changed the primary alias, select Remove next to the affected email address to remove it from your account.
Once your email address is no longer associated with your Microsoft account, restart your device and open Outlook.

 From what we have seen, the issue is not because the email address is set as Primary on the Microsoft account, but that it is connected to it in the first place. That is why after adding the new email address to the account, you must make it the new primary so you can completely removed your Hosted Exchange email address from the account. There-by completely severing the connection.