Exchange 2010 environment fully patched. One user hit the 10 device threshold on Exchange activesync devices and IT was tasked with removing the association from that device.

Right-click on the user and manage mobile device. Attempt to remove the partnership (not remote wipe) and had an error:
The ActiveSyncDevice Cannot be Found.

Awesome.

Powershell to the rescue:
List all devices for an account
get-activesyncdevice -mailbox USERNAME | select DeviceID, Identity

List all details for those devices
get-activesyncdevicestatistics -mailbox USERNAME

Remove that activesync
Remove-ActiveSyncDevice -Identity $(Get-ActiveSyncDevice -Mailbox USERNAME | where {$_.DeviceId -like "DEVICEID"} | select Identity).identity

Apparently what happens is that when we decided to move all OU groups around (and memberships) Exchange doesn’t like that very much and forgets to update itself.
http://exchangeblog.pl/en/2013/01/exchange-2010-remove-mobile-device-error-the-activesyncdevice-cannot-be-found/