Isso inclui:

• Números internacionais?
• Extensões?
• Outras informações além do número real (como "pedir bobby")?

Se tudo isso for não, eu usaria um campo de 10 caracteres e removeria todos os dados não numéricos. Se o primeiro for um sim e os outros dois não, eu usaria dois campos varchar(50), um para a entrada original e outro com todos os dados não numéricos distribuídos e usados ​​para indexação. Se 2 ou 3 forem sim, acho que faria dois campos e algum tipo de analisador maluco para determinar o que é extensão ou outros dados e lidar com isso adequadamente. Claro que você poderia evitar a segunda coluna fazendo algo com o índice onde ele retira os caracteres extras ao criar o índice, mas eu apenas faria uma segunda coluna e provavelmente faria a remoção de caracteres com um gatilho.

Atualização:para resolver o problema do AJAX, pode não ser tão ruim quanto você pensa. Se esta for realmente a principal maneira de fazer algo na tabela, armazene apenas os dígitos em uma coluna secundária como eu disse e, em seguida, torne o índice dessa coluna o clusterizado.