Use a data/hora atual e um rand ao final. Quando converter para letras, ficará bem pequeno. É bom que é ordenável.
Outra possibilidade é você ter uma tabela de ids. Sempre que requisitar um, marque-o como utilizado. Nunca se repetirá e você poderá acompanhar o andamento pra saber quando estiver perto de acabar e você poderá gerar novos para a tabela.
Obrigado pelo seu comentário! Vou fazer um teste com essa ideia de utlizar data/hora com um rand no final, um grande ponto que preciso ver seria as chances de colisōes dos ids gerados dessa forma.
No algoritmo que coloquei na publicação a média tem sido de 3 a 5 colisōes a cada 100 mil ids gerados, então pode ser possível se diminuir ainda mais as chances.
Mas acho que essa técnica também acabaria levando para as mesmas trativas de checar se ja existe o id no banco, fazer um loop até encontrar um que não existe e limitar o número de tentativas pra evitar casos extremos.
Fora isso, eu não tinha pensado na sua segunda ideia em ter uma tabela de ids já populada com as opçōes, farei alguns testes com essa solução.