Active Sync doesn’t work for some users on Exchange 2010/2013

Recently our team had a case where some users started complaining that they cannot configure Windows Phone / Android 5 devices to connect to mixed environment Exchange 2010 with Exchange 2013. Exactly same accounts didn't had problems to connect on other devices with iOS or older. If that wasn't enough an account correctly working on iOS was giving errors when tested with Microsoft Remote Connectivity Analyzer which is superior tool when testing such cases. It was displaying an error on Folder Sync which is the last test step for a test to be successful. Error:

[System.Net.WebException]: The remote server returned an error: (500) Internal Server Error.

Followed by:

X-ExceptionDiagnostics: Microsoft.Exchange.AirSync.AirSyncPermanentException —> Microsoovision,ResolveRecipients,ValidateCert ft.Exchange.Data.Directory.ADOperationException: Active Directory operation failed on AD2.GLOBAL.LOCAL. This error is not retriable. Additional information: Access is denied.%0d%0 aActive directory response: 00000005: SecErr: DSID-03152610, problem 4003 (INSUFF_ACCESS_RIGHTS), data 0%0a —> System.DirectoryServices.Protocols.DirectoryOperationException: The user has insufficient access rights.%0d%0a at System.DirectoryServices.Protocols.LdapConnection

Also same error was visible during different actions done by users via OWA/ECP, especially when they tried to remove their devices:

Active Directory operation failed on This error is not retiable. Additional informaiton: Active Directory response: 00000005: SecErr:DSID-03152485, problem 4003 (INSUFF_ACCESS_RIGHTS)

Generally such errors typically fixed by checking the box “Allow inheritable permissions …”. However this has not solved the problem for us. After going back and forth and trying different solution the culprit was found in Active Directory. The simple fix is to give Exchange Servers group proper permissions for msExchActiveSyncDevices objects. What is important here is to make sure it's correct object because there is also msExchActiveSyncDevice (without s) higher in the list which makes it the first choice (as it did for us – and it doesn't fix the issue). First you need to enable Advanced Features view in Active Directory Users and Computers. Start Active Directory Users and Computers. Click View, and then click to enable Advanced Features. Right-click the object where you want to change the Exchange Server permissions, and then click Properties. And then you can change it for the user in question, and if it works deploy it as a solution in the root of your domain. On the Security tab, click Advanced. Click Add, type Exchange Servers, and then click OK. In the Apply to box, click Descendant msExchActiveSyncDevices objects. Under Permissions, click to enable Modify Permissions. Click OK three times. After applying the fix Microsoft Remote Connectivity Analyzer gave the Green Light!