The Deletion Type for the User business object is set to Soft deletion. This means that when you delete a user, the record is not actually deleted from the database, but has its Is Deleted attribute set to True. The record then no longer appears in lists, and can no longer be selected, but references to it still remain. This means that if a user leaves the organization, their record is soft deleted, so that they can no longer be selected, but existing references to them remain.
If required, you can restore user records that have been soft deleted by right-clicking them in a query that shows soft deleted records, then clicking Restore.
For more information about creating a query to enable you to restore soft deleted records, see the Designer Guide.