When follow instructions in this link to recover a deleted object, I got error message "illegal modify operation". One of the workaround in the comment worked for me (the restore-adobject method): add a -NewName argument in the restore-adobject statement.
LDAP method didn't work well as it showed only first 1000 objects under "deleted objects" container while we had way more that number.