Assuming you have some sort of formula for generating a key and assuring the key is valid, in whatever area they are supposed to enter the key and create their user id, have them enter the key and id. Then, check 2 things, first that the key is valid, second that the key hasn''t been used before. As for keeping track of if it has been used, you just need some kind of database with all of the used IDs so far.

If there is no formula and you want to just randomly generate keys, the database could initially contain all of the Keys, and one column of that table could be a flag of if the key has been used to generate an ID already.