Wenn es nur gibt 10-30% der Nummern schon vergeben - dann heißt das nur 10-30 % der Abfragen werden mindestens zweimal durchgeführt. Was überhaupt kein großes Leistungsproblem ist.
Andernfalls - erstellen Sie einfach eine Listentabelle mit allen 5 Ziffern (nur 100.000 Zeilen) und entfernen Sie alle vorhandenen. Wenn Sie eine andere Zufallszahl benötigen, wählen Sie einfach eine aus und löschen Sie sie.