Isso parece um problema desde o início. Qualquer tipo de pesquisa que você fizer exigirá uma varredura de tabela e todos sabemos que isso é ruim.

Que tal adicionar uma coluna com um hash dos números de telefone atuais depois de remover todos os caracteres de formatação. Então você pode pelo menos indexar os valores de hash e evitar uma varredura completa da tabela.

Ou a quantidade de dados é pequena e não se espera que cresça muito? Então talvez apenas sugando todos os números para o cliente e executando uma pesquisa lá.