Remove ActiveSyncDevice Fails after restore user in Active Directory

The other day i had an issue at customer site that complain about two ActiveSync issues:

1. User cannot sync with new device.
2. Administrator cannot remove Active Sync device from user.

Both issues came from the same user, that was restored from backup couple of days before.
First issue was fixed by adding inheritance permissions for the object in Active Directory Users and Computers and in ADSI Edit. from some reason the backup software didn't set this automatically.

Second issue was a little bit tricky.
When the administrator tried to remove old devices for that user he got a failure message that device cannot be found:

Running Get-ActiveSyncDeviceStatistics for the same user discover eight devices:

Browsing to ExchangeActiveSyncDevices under the user in ADSI Edit discover only one device:

It looks like the backup software didn't restore all properties for that user, that includes ActiveSync Devices.
To fix that issue i decided to manually create those devices in ADSI Edit:

Paste the device ID. for example:

After adding all devices it looks like that:

Then i was able to successfully remove old devices: