Also I have tried doing the change using ADSI script:
[Reflection.Assembly]::LoadWithPartialName("Softerra.Adaxes.Adsi")
$admNS = New-Object "Softerra.Adaxes.Adsi.AdmNamespace"
$admService = $admNS.GetServiceDirectly("localhost")
# Bind to user object
$userDN = "CN=company,DC=com"
$user = $admService.OpenObject("Adaxes://$userDN", $NULL, $NULL, 0)
# Create an instance of the AdmExchangeMailboxParameters class
$mailboxParams = New-Object "Softerra.Adaxes.Adsi.Exchange.AdmExchangeMailboxParameters"
# Automatically update e-mail addresses based on e-mail address policy
$mailboxParams.EmailAddressPolicyEnabled = $False
$user.SetMailParameters($mailboxParams, "ADM_SET_EXCHANGE_PARAMS_FLAGS_NONE")
But the result is the same. This was run on the account with Domain Admin and Enterprise Admin permissions.