maneira inteligente de gerar um número aleatório único

Eu quero gerar uma sequência de números aleatórios únicos no intervalo de 00000001 a 99999999.

Portanto, o primeiro pode ser 00001010, o segundo 40002928 etc.

A maneira mais fácil é gerar um número aleatório e armazená-lo no banco de dados e, na próxima vez, faça-o novamente e verifique no banco de dados se o número já existe e, se houver, gere um novo, verifique-o novamente, etc. não parece certo, eu poderia estar regenerando um número talvez 100 vezes se o número de itens gerados for grande.

Existe uma maneira mais inteligente?

EDITAR como sempre, eu esqueci de dizer POR QUE eu queria isso, e provavelmente tornará as coisas mais claras e talvez obtenha uma alternativa, e é: queremos gerar um número de ordem para uma reserva, para que possamos usar 000001, 000002 etc. não queremos dar aos concorrentes uma idéia de quanto pedidos são criados (porque não é um mercado de alto volume e não queremos que eles saibam se estamos no pedido 30 após 2 meses ou no pedido 100. Portanto, queremos ter um número de pedido aleatório (mas único)