As far as I'm aware, the "full user deletion" doesn't actually delete the user fully, the reasons for which have been extensively discussed here and on the Moodle forums. From the sound of things, the users in question as being "fully deleted" which makes their account unrecoverable and changes their username to the string you see. From the page you highlighted, the description is "during full delete username, email and ID number are discarded - this means that accounts cannot be undeleted later." If you change the deletion option on there to "keep username, email and ID number", then the users just have the "deleted" flag set on their account, and can be undeleted later on.
Dan