Acho que você está caindo na armadilha da otimização prematura.

Antes de otimizar, você precisa de métricas para identificar quais áreas do seu sistema estão precisando de aprimoramentos. Depois disso, você pode identificar quais são os aprimoramentos que realmente valem a pena implementar. Talvez você nem tenha problema algum de desempenho e vá adicionar complexidade desnecessária ao seu sistema. Talvez precise aumentar o desempenho, mas esteja focado no local errado. Por isso, primeiro precisamos das métricas de desempenho para depois poder aprimorar.

Pequena nota: quando você diz:

O dado do usuário irá percorrer toda a lista até achar seu idêntico na tabela, retornando um valor para a aplicação. Para que não percorra milhares de itens toda vez, planejo dividir em várias pequenas tabelas que se iniciam com a letra do alfabeto, e sequência de dois caracteres, (A, B, C… AA, AB, AC...).

Este método funcionaria caso a distribuição dos seus links seja normalizada. Caso contrário, você vai acabar sobrecarregando uma das tabelas. Por exemplo, se os valores tenderem a iniciar com a letra A, você terá uma tabela A muito maior do que as restantes e não ajudará em desempenho (pelo contrário, pode piorar). Existem maneiras de fazer particionamento no banco de dados mesmo. Alem do mains, indices já organizam dados em árvores balanceadas, outro motivo para não fazer este tipo de otimização. Caso realmente você precise, teria que calcular um hash balanceado para depois poder quebrar em outras tabelas.