Unable to delete AD account (using Domain Admin account)

I am unable to delete a user in AD. I tried in GUI and also in powershell using a domain admin account but I still cannot delete it. This is the error message in powershell:

The directory service can perform the requested operation only on a leaf object

It looks like it has an Active Sync device tied up on the account, however we already deleted the mailbox of the user, so even if we query in exchange powershell, it would say user not found.

The user is not on a “protected OU”, it was before but we already moved it to a different OU.

So now, my main problem is how to remove the active sync device that is tied up on his account. I already extracted a list of all mobile devices in exchange and I cannot find the user

Thanks in advance!