Suppose an organization that started out with Built-in users now wants to implement Single Sign-on (Enterprise) logins. The naming convention for their Lightweight Directory Access Protocol (LDAP) with the ArcGIS Online shortname may default to the same usernames that the built-in users had. When a new user sets up their Enterprise account in ArcGIS Online, it requires them to create a new username because the old one is taken.
This is due to the fact that whenever an account is enabled for Esri Access within an ArcGIS Online Organization, and then is deleted from the organization, that account gets converted into a public account, therefore the username is taken. Therefore, the organization must have enabled Esri Access for the accounts and then deleted them, which converted the accounts to public, therefore the usernames are taken.
Note: If the person with the username that is to be deleted does not remember which email was used to create the account, simply go through the Forgot username? link in the Sign In page to have Esri send the email to all associated accounts; it specifies which one is Public.