Outlook Authentication Issues with Exchange Online

I'm not sure if the problem could have been solved in another way but I am going to present you what finally worked for me. It seemed that the user's mailbox was damaged somehow. I still don't know exactly what the problem was. So my solution finally was to re-create the users's mailbox.

Export the users's email to a pst-file using the Exchange Management Shell:

New-MailboxExportRequest -Mailbox "username" -FilePath "\\path-to-share\filename.pst"

You can check the status using:

Get-MailboxExportRequest | Get-MailboxExportStatistics | fl

It may happen that either the ExportRequest or the ImportRequest gets stuck in the status "Queued". In my case I had some other ExportRequests in my Get-MailboxExportRequest result. You may remove the completed requests using this command per example:

Get-MailboxExportRequest -Status Completed | Remove-MailboxExportRequest

or a specific one using this:

Remove-MailboxExportRequest -Identity "OU\structure\to\useraccount\MailboxExport1"

After I removed all other requests the status of the desired request changed from "Queued" to "In Progress".

Once the export is completed we need to disable the user's mailbox first. Be aware that removing the mailbox before it was disabled would also remove the whole active directory user account. The disabling removes the connection between the user account and the mailbox.

Disable-Mailbox -Identity "username"

Now we need the MailboxGuid of the disabled mailbox. We can list the disabled mailboxes on our exchange database using:

Get-MailboxStatistics -Database “Mailbox Database Name" | where {$_.disconnectdate -ne $null} | select displayname,MailboxGUID

In my case (Microsoft Exchange Server 2013 CU4 (SP1)) the disabled mailbox wasn't in the list so I listed all other mailboxes which in my case is still OK because I don't have that many. Other users may need to use a more specific filter in their command:

Get-MailboxStatistics -Database “Mailbox Database Name" | where {$_.disconnectdate -eq $null} | select displayname,MailboxGUID

However I found the user's mailbox and copied the MalboxGuid. Then I removed it using:

Remove-Mailbox -Database “Mailbox Database Name" -StoreMailboxIdentity 92d20afd-42d8-496e-9455-34b3d6cb066e

The user's mailbox is now deleted and we are ready to create a new one. I simply logged into "ECP" and created a new mailbox for the user. After the Mailbox got created we are ready to import the exported emails into the new mailbox using:

New-MailboxImportRequest -Mailbox "username" -FilePath "\\path-to-share\filename.pst"

As before the status of this procedure can be checked using:

Get-MailboxImportRequest | Get-MailboxImportStatistics | fl

After the Import is finished I would recommend to delete the user's outlook profile and create a new one. In my case it was still buggy before I did this, and I also removed and re-assigned the permissions to other mailboxes for the user, just in case.

One last thing: After the whole procedure it happened that internal users who tried to send emails to the user's email account got an "email could not be delivered" error. I think this is because the MailboxGuid of course has changed and the server still tries to deliver the emails to the old mailbox. The users who are trying to send an email to the user's mailbox needed to get the latest changes in their offline address book done. It doesn't seem to affect all users but some, so I created a tutorial for the affected users and sent it to them if they reported the error.

I hope this will help someone who's also unlucky to have the same problem.