Deleting and Restoring a Contact detaches Contact from User
It's on purpose that it removes the link to the user when you delete. It was added years ago here: https://github.com/civicrm/civicrm-svn/commit/3d9843c5912cb9d77e557b4a8cd4ef711f2cdcbb

and seems related to deduping https://issues.civicrm.org/jira/browse/CRM-6861

But yes Civi will reattach them once you do something that triggers the matching which is usually on email address, i.e. if the drupal user and the contact record have the same email.