Christopher,
Deleted Users actually do not go to the Recycle Bin because they never get fully deleted. This is due to possible time and effort added by the user on past work items. Deleting the User would break the calculations for the ones the user was a resource on.
Deleted Users are simply marked as deleted and removed for your view. In order to see deleted users, go to the People Module and in the Filter, select to view Deleted Users. You can then restore the user if you wish.
Sincerely,
Boris Krutiy
Comment actions