As you are seeing, users are never completely deleted from Windchill when you delete a user. Rather the entry in the WTUser table is updated to include the "(deleted)" text (along with a few other updates to that entry to indicate that the user is deleted and cannot log into Windchill. This is done to preserve data integrity for objects that were owned/created/modified by that user.
I don't know of a way to change that text OOTB. It would require some sort of customization if it can be done.