Jika ada hanya 10-30% angka sudah diambil - berarti hanya 10-30% kueri akan dilakukan setidaknya dua kali. Yang sama sekali bukan masalah kinerja yang besar.
Jika tidak - buat saja tabel daftar semua-5-digit-angka (hanya 100rb baris) dan hapus semua yang ada. Saat Anda membutuhkan nomor acak lain - cukup pilih satu dan hapus.