A customer recently reported a problem to Microsoft where they were dicovering that their exchange web services were unable to connect to some mailboxes.

Often support engineers need to ask probing questions about what recently happened in the companys organisation, what recent tools and software updates that were applied and some back ground information about their network topology is neeed to be able to isolate the problem at hand. In this customers case, they had recently performed a migration from 1900 exchange 2003 mailbox accounts to exchange 2010 mailboxes.

Some of these accounts were unable to be accessed using impersonation from exchange web services
I wanted to document some tools and questions that might be worth asking to try and help isolate the root cause and be able to find an appropriate troubleshooting path. The core issue was related to impersonation code not working in customers EWS code to access certain mailboxes.

these articles are a good reference to determine how you can get configure impersonation to work with EWS and ensure the accounts you are using have the appropriate privileges/roles.scope to perform the task
http://msdn.microsoft.com/en-us/library/bb204095.aspx

Using Exchange Impersonation
http://msdn.microsoft.com/en-us/library/bb204088.aspx

Working with impersonation by using the EWS Managed API
http://msdn.microsoft.com/en-us/library/dd633680(EXCHG.80).aspx

The soap test tool is a good tool to determine (outside of yoru code) if your EWS code is working correctly, you can find this here -http://soaptestapp.codeplex.com/
There is a brief introduction here: http://soaptestapp.codeplex.com/wikipage?title=Introduction

With the call succeeding we can rule out if it was related to the customers code so we wanted to know what ServiceError reports back from EWS
http://msdn.microsoft.com/en-us/library/microsoft.exchange.webservices.data.serviceerror(v=exchg.80).aspx
In the SOAP requests in your code can you add..

svc.TraceEnabled = true;
svc.TraceFlags |= TraceFlags.All;

more information here - Tracing EWS requests
http://msdn.microsoft.com/en-us/library/dd633676(v=EXCHG.80).aspx
This will add additional logging information to the SOAP data

chck that the customer was using the latest EWS API libraries(14.02.0051.000)
http://www.microsoft.com/download/en/details.aspx?id=13480

It's always good to understand what the underlying SOAP requests are so using tools such as netmon and fiddler is always good to use to determine what web service errors you may be seeing .

These mailboxes were exchange 2003 mailboxes that have been moved over to Exchange 2010 so fiddler was used to determine what network information was given - http://www.fiddler2.com/fiddler2/

Always good to see if there were any system event logs from the machines performing the migration process, were there any corruptions? missing objects?

We narrowed down the code and took away the impersonation aspects to rule out accounting issues. We ran the account taking away the impersonation and noticed some of the accounts worked. We double checked the Role assignments to ensure the account was using the right role

New-ManagementRoleAssignment –Name:<name> –Role:ApplicationImpersonation –User:<domain user>
(no scope filter)

Which then led us to the permissions of the account itself and we needed to check that the impersonating service account had ms-Exch-EPI-Impersonation and ms-Exch-EPI-May-Impersonate permissions set on all the CAS servers and that all exchange are members of Windows Authorization Access Group.

We needed to compare the working and non-working mailboxes so we used this cmdlet to understand the differences.
Get-MailboxDatabase | ForEach-Object {Get-ADPermission -Identity $_.DistinguishedName -User <service> }
http://technet.microsoft.com/en-us/library/bb125183.aspx

This lists down all the mailboxes and may shows ones that may have Explicit Deny on the ones in question. Quite possible an odd access control entry on those account objects exists in the AD that are not present on the others that is causing failure in the AuthZ calls (an explanation of this is in the article below). For impersonation and the service account access failing like that indicates that the underlying AuthZ calls that EWS performs failed for one reason or another. 
http://support.microsoft.com/kb/331951

The result of this led us to believe that the mailboxes in questions that weren't working were linked mailboxes compared to standard user mailboxes.

In this case, the customer performed the migration but in the process of migrating Mailboxes from an Exchange 2003 enviroment to Exchange 2010, some of the mailboxes have been coming over as linked mailboxes and not users mailboxes. if you do come across this, here is how you can reset this. (might be worth adding as part of your migration process).

All linked mailboxes have the LinkedMasterAcount to set.
Open up the EMS as Administrator
To see the LinkedMasterAccount run this command “Get-User -Identity ”user” | FL LinkedMasterAccount
Run the following command “Set-User -Identity ”user” -LinkedMasterAccount $null” This command will not have any output, but it will set the LinkedMasterAccount to null
To verify run the same Get-User command from above.
The account will now show as a User Mailbox and not a Linked Mailbox
By resetting the linked mailboxes meant that the EWS calls succeeeded.

Listing the errors that you are most likely during this (SEO indexing)

Response (failed: not found):
Error occurred: The remote server returned an error: (404) Not Found.
Response (failed: Connection did not succeed):
You do not have permission to view this directory or page.
HTTP/1.1 405 Method Not Allowed
The page you are looking for cannot be displayed because an invalid method (HTTP verb) is being used.
HTTP/1.1 401 Unauthorized
You do not have permission to view this directory or page.