Maneira mais rápida de remover caracteres não numéricos de um VARCHAR no SQL Server

Estou escrevendo um utilitário de importação que está usando números de telefone como uma chave exclusiva dentro da importação.

Eu preciso verificar se o número de telefone já não existe no meu banco de dados. O problema é que os números de telefone no banco de dados poderiam ter coisas como traços e parênteses e possivelmente outras coisas. Eu escrevi uma função para remover essas coisas, o problema é que élento e com milhares de registros no meu banco de dados e milhares de registros para importar de uma só vez, esse processo pode ser inaceitavelmente lento. Eu já fiz a coluna do número de telefone um índice.

Eu tentei usar o script desta postagem:
T-SQL trim & nbsp (e outros caracteres não alfanuméricos)

Mas isso não acelerou nada.

Existe uma maneira mais rápida de remover caracteres não numéricos? Algo que pode ter um bom desempenho quando 10.000 a 100.000 registros precisam ser comparados.

Tudo o que é feito precisa executarvelozes.

Atualizar
Dado o que as pessoas responderam, eu acho que vou ter que limpar os campos antes de executar o utilitário de importação.

Para responder a pergunta sobre o que estou escrevendo o utilitário de importação, é um aplicativo C #. Estou comparando o BIGINT ao BIGINT agora, sem necessidade de alterar os dados do banco de dados, e ainda estou obtendo um resultado de desempenho com um conjunto muito pequeno de dados (cerca de 2000 registros).

Poderia comparar o BIGINT ao BIGINT estar diminuindo as coisas?

Eu otimizei o lado do código do meu aplicativo tanto quanto eu posso (removi regexes, removi chamadas DB desnecessárias). Embora eu não possa mais isolar o SQL como a origem do problema, ainda sinto que é.

questionAnswers(15)

yourAnswerToTheQuestion