When you delete users who were part of a department in an environment where Department Access Control is enabled, they are displayed as "User (Not Visible)" for users who currently belong to the department.
Department Access Control

When users are deleted, they will lose their department information and be in the state where they do not belong to any department.
Therefore, if the Department Access Control is enabled, the users who are part of the department will no longer be able to view the display names of the deleted users (those who do not belong to any department).
On the contrary, the users who do not belong to any department will be able to view the display names of the deleted users (those who do not belong to any department).

If you want to continue to display the name of former users in the department, such as users who are no longer working for your company, consider making the state of the users "Inactive" instead of deleting them.
Deactivating or Reactivating Users