Currently, we leave an orphaned civicrm_uf_match record when the CMS User is deleted. In Drupal, I think we can delete this based on a user_hook op. Not sure if we can fix for Joomla.
The result of this is that the contact/view screen contains a "View User" link to a non-existent user record.
(Lobo - assigning to you in case there's a reason why we didn't or can't fix this in reasonable way).