você pode resolver isso com conversão de base.
igual a gente faz de base binaria x decimal x hexadecimal, você pode trabalhar com um "número" de 36 algarismos (os numeros em sí e as letras do alfabeto).

no banco de dados, você continua utilizando os identificador decimal, até porque isso melhorar a indexação.

mas o que você apresenta para o usuario é a conversão desse número.

exemplo:
de 0 a 9, você vai ter 0 a 9 mesmo.
a partir daí que verá a diferença..

o 10 equivale a "a", o 11, "b" e assim por diante.

mas como no seu caso precisará de 6 digitos sempre, pode incluir na conversão uma adição para que id 1 seja equivalente a 100000.
(e quando converter do uid para decimal, não esqueça de subtrair).

assim, não tem risco de duplicar e elimina a necessidade de verificar a disponibilidade no banco de dados.