Ако има само 10-30% от числата вече са заети - тогава това означава, че само 10-30% от заявките ще бъдат изпълнени поне два пъти. Което изобщо не е голям проблем с производителността.
В противен случай - просто създайте таблица с всички 5-цифрени числа (само 100k реда) и премахнете всички съществуващи. Когато имате нужда от друго произволно число - просто изберете едно и изтрийте.