Recently we tried to replace a users phone and when adding his Exchange mail we got the message
have 10 phone partnerships out of the maximum allowed 10 partnerships. After
you reach the maximum, you can't create additional partnerships until you
delete existing ones from your account. To do so, sign in to Outlook Web App,
click Options > Phone > Mobile Phones, and delete any unused
However when trying to remove old devices we received the message "The ActiveSyncDevice Cannot be Found"
Thanks to this post we found our solution. Exchange 2010 remove mobile device Error The ActiveSyncDevice Cannot be Found