Okay the first thing to is to try https://testconnectivity.microsoft.com/
If a server error 500 occurs it might be related to the fact that the user is in a protected group, and thus some inheritance gets removed every hour..
From http://technet.microsoft.com/en-us/library/dd439375%28EXCHG.80%29.aspx
To check whether inheritance is disabled on the user:
Open Active Directory Users and Computers.
On the menu at the top of the console, click View > Advanced Features.
Locate and right-click the mailbox account in the console, and then click Properties.
Click the Security tab.
Click Advanced.
Make sure that the check box for "Include inheritable permissions from this object's parent" is selected.
Try also to remove the phone from the mail user.
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.
Best Answer
Apparently Mac Mail uses both Active Sync and EWS to connect to exchange; because of this it will not show up as a device on the management side. Disabling EWS prevents Mac Mail from connecting while still allowing Active Sync devices to connect.