А>с точки зрения обывателя, в чём несправедливость? Кто получает изначальное преимущество или как его можно получить?

ок, нужно тогда спросить, хотим ли мы равномерного распределения выигрыша при уже имеющейся раздаче паспортов. Или нас устроит равномерное распределение выигрыша, считая что само распределение номеров паспортов уже изначально случайно и включено в "справедливость".

В первом случае, так как номера существующих паспортов распределены неравномерно, то в зависимости от алгоритма преимущество может получать, скажем, тот номер, у которого нет близких соседей. И для достижения справедливости придется тестировать существование каждого номера.

Во втором случае собственно никаких случайных цифр и генерировать не нужно. Достаточно сказать -- победил самый маленький номер, и начать тестировать начиная с 0 пока не наткнемся на победителя.