Check the following attribute in <D
ropertyupdate> request
<b:0x6849001F>/o=First Organization/ou=First Administrative Group/cn=RECIPIENTS/cn=...</b:0x6849001F>
The value should read exactly as the value of legacyExchangeDN of the contact representing the Zimbra user.
Also open up Active Directory Users and Computers, locate the contact representing the Zimbra user, look at Email Addresses tab and Exchange General tab and make sure the email address is correct, and the alias is the same as cn in legacyExchangeDN.