Se houver apenas 10-30% dos números já obtidos - significa que somente 10-30% das consultas serão realizadas pelo menos duas vezes. O que não é um grande problema de desempenho.

Caso contrário - basta criar uma tabela de lista de números de 5 dígitos (apenas 100 mil linhas) e remover tudo o que existe. Quando você precisar de outro número aleatório - basta escolher um e excluir.