Есть ли смысл делать поиск на похожу рандомно сгенерированную строку?
0) Задачу опишите, для чего это вам?
1) Да, может, и вероятность достаточно высокая. Если принципиально работать именно с цифрами проверка обязательна.
2) Для генерации рандомных ключей лучше использовать хеш, а не цифровой ключ. У него коллизии гораздо менее вероятны (хотя тоже не нулевые). 
3) Обычно используют пары значений (например логин и пароль) для большей уникальности.

И вопрос остается открытым - зачем?
пробегаться не нужно, достаточно условие уикальности по insert into и повтора после exeption
ну или select / insert

но сама логика выбрана криво и зависит от полноты массива данных

P.S. если очень хотца  - можно через Фильтр Блума прогонять, это быстрее