static void UpdateContact()
{
    // Create the bindings and set the credentials.
    ExchangeServiceBinding esb = new ExchangeServiceBinding();
    esb.Url = "http://fqdn/ews/exchange.asmx";

    esb.Credentials = new NetworkCredential("UserName", "Password", "Domain");

    // Create an object of update item type.
    UpdateItemType updateItemType = new UpdateItemType();
    updateItemType.ConflictResolution = ConflictResolutionType.AlwaysOverwrite;

    updateItemType.ItemChanges = new ItemChangeType[1];
    ItemChangeType changeType = new ItemChangeType();

    // Get the ID and change key from the contact item that you btained by using FindItem or CreateItem.
    ItemIdType contactId = new ItemIdType();
    contactId.Id = "AAAt=";
    contactId.ChangeKey = "EQAA";

    changeType.Item = contactId;

    changeType.Updates = new ItemChangeDescriptionType[1];

    // Create a set item field to identify the type of update.
    SetItemFieldType setItem = new SetItemFieldType();
    PathToIndexedFieldType indexedField = new PathToIndexedFieldType();

    // Update EmailAddress1 for the contact.
    indexedField.FieldIndex = "EmailAddress1";
    indexedField.FieldURI = DictionaryURIType.contactsEmailAddress;

    setItem.Item = indexedField;

    // Create a contact item to contain the update.
    ContactItemType contact = new ContactItemType();
    contact.EmailAddresses = new EmailAddressDictionaryEntryType[1];

    // Specify the e-mail address to be modified, and specify the new e-mail address.
    EmailAddressDictionaryEntryType emailAddress = new EmailAddressDictionaryEntryType();
    emailAddress.Key = EmailAddressKeyType.EmailAddress1;
    emailAddress.Value = "donhall@example.com";

    contact.EmailAddresses[0] = emailAddress;

    setItem.Item1 = contact;
    changeType.Updates[0] = setItem;
    updateItemType.ItemChanges[0] = changeType;

    // Send the update item request and receive the response.
    UpdateItemResponseType updateItemResponse = esb.UpdateItem(updateItemType);

    // Access the response.
    if (updateItemResponse.ResponseMessages.Items.Length > 0 &&
        updateItemResponse.ResponseMessages.Items[0].ResponseClass == ResponseClassType.Success)
    {
        ItemInfoResponseMessageType responseMessage = updateItemResponse.ResponseMessages.Items[0] as ItemInfoResponseMessageType;
        ContactItemType contactResponse = responseMessage.Items.Items[0] as ContactItemType;
        Console.WriteLine("Created Contact Item with Id {0} and ChangeKey {1}", contactResponse.ItemId.Id, contactResponse.ItemId.ChangeKey);
    }
}

<?xml version="1.0" encoding="utf-8"?>
<UpdateItem xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
                xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
                ConflictResolution="AlwaysOverwrite">
  <ItemChanges xmlns="http://schemas.microsoft.com/exchange/services/2006/messages">
    <ItemChange xmlns="http://schemas.microsoft.com/exchange/services/2006/types">
      <ItemId Id="AAAt=" ChangeKey="EQAA" />
      <Updates>
        <SetItemField>
          <IndexedFieldURI FieldURI="contacts:EmailAddress" FieldIndex="EmailAddress1" />
          <Contact>
            <EmailAddresses>
              <Entry Key="EmailAddress1">donhall@example.com</Entry>
            </EmailAddresses>
          </Contact>
        </SetItemField>
      </Updates>
    </ItemChange>
  </ItemChanges>
</UpdateItem>

<?xml version="1.0" encoding="utf-8"?>
<UpdateItemResponse xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
                        xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <ResponseMessages xmlns="http://schemas.microsoft.com/exchange/services/2006/messages">
    <UpdateItemResponseMessage ResponseClass="Success">
      <ResponseCode>NoError</ResponseCode>
      <Items>
        <Contact xmlns="http://schemas.microsoft.com/exchange/services/2006/types">
          <ItemId Id="AAAt=" ChangeKey="vom6O" />
        </Contact>
      </Items>
    </UpdateItemResponseMessage>
  </ResponseMessages>
</UpdateItemResponse>