Seria melhor armazenar uma tabela com todos os 10.000 valores possíveis definidos e um sinalizador "em uso" em cada um. Dessa forma, liberar o número para reutilização é uma atualização simples para definir "inuse=false".
Também torna simples encontrar o menor valor disponível
SELECT idstring
FROM idstringtable
ORDER BY idstring ASC
WHERE (available = 1)
LIMIT 1
Fazer isso com bloqueios/transações apropriados impediria que duas ou mais solicitações obtivessem o mesmo ID e, como é uma tabela pequena, fazer um bloqueio de tabela global não afetaria significativamente o desempenho.
Caso contrário, você ficaria preso vasculhando sua tabela de usuários, tentando encontrar a primeira "lacuna" na sequência de numeração.
