Unable to restore a recently deleted user.
As per error, this is happening because Object’s parent organizational unit no longer exists, It has to be restored first.
First Locate Parent, Restore that first
Try restoring again, and now you will see that account get successfully restored.
Note – You would have to perform such parent restore to restore the hierarchy before restoring actual user.