Isso é muito estranho, eu mesmo lutei com esse problema muitas vezes, nos últimos 15 anos e geralmente desenvolvi estruturas que separam códigos de área, códigos de país e números em campos separados, etc. Mas enquanto lia sua pergunta, outra solução apareceu na minha cabeça, requer um campo separado, embora possa não ser apropriado para você.

Você poderia ter um campo separado chamado reverse_phone_number, ter isso preenchido automaticamente pelo mecanismo de banco de dados, então, quando as pessoas pesquisarem, simplesmente inverter a string de pesquisa e usar o campo reverso indexado com apenas um % no final da string semelhante, permitindo assim o uso do índice.

Dependendo do seu mecanismo de banco de dados, você poderá criar um índice baseado em uma função definida pelo usuário que faça o inverso para você, eliminando a necessidade de um campo adicional.

Em alguns países, por ex. no Reino Unido, você pode ter um problema com zeros à esquerda. Um número de telefone do Reino Unido é representado como (código de área) (Número de telefone), por exemplo 01634 511098, quando esta é internacionalizada o zero inicial do código de área é removido e o código de discagem internacional (+ ou 00) e o código do país (44) são adicionados. Isso resulta em um número de telefone internacional de +441634511098. Qualquer usuário que procurasse por 0163451109 não encontraria o número de telefone se ele fosse digitado em formato internacionalizado. Você pode superar esse problema removendo zeros à esquerda da string de pesquisa.

EDITAR Com base nas sugestões de Ollie Jones, você deve armazenar o número conforme inserido pelo usuário e, em seguida, retirar zeros à esquerda, pontuação e espaço em branco do número antes de reverter e armazenar no campo invertido. Em seguida, basta usar o mesmo algoritmo para remover a string de pesquisa antes de reverter, encontrar o registro e exibir o número originalmente inserido de volta ao usuário.