Sie sollten besser eine Tabelle speichern, in der alle 10.000 möglichen Werte definiert sind, und für jeden ein "In-Use"-Flag. Auf diese Weise ist die Freigabe der Nummer zur Wiederverwendung ein einfaches Update, um "inuse=false" zu setzen.
Macht es auch einfach, den niedrigsten verfügbaren Wert zu finden
SELECT idstring
FROM idstringtable
ORDER BY idstring ASC
WHERE (available = 1)
LIMIT 1
Dies mit entsprechenden Sperren/Transaktionen zu tun, würde verhindern, dass zwei oder mehr Anfragen dieselbe ID erhalten, und da es sich um eine kleine Tabelle handelt, würde eine globale Tabellensperre die Leistung nicht wesentlich beeinträchtigen.
Andernfalls würden Sie in Ihrer Benutzertabelle herumwühlen und versuchen, die erste "Lücke" in der Nummerierungssequenz zu finden.