Това изглежда като проблем от самото начало. Всяко търсене, което правите, ще изисква сканиране на таблицата и всички знаем, че това е лошо.
Какво ще кажете за добавяне на колона с хеш на текущите телефонни номера след премахване на всички символи за форматиране. Тогава можете поне да индексирате хеш стойностите и да избегнете пълно сканиране на таблицата.
Или количеството данни е малко и не се очаква да нарасне много? Тогава може би просто изсмуквате всички числа в клиента и извършвате търсене там.