Se você realmente deseja definir similaridade da maneira exata que você formulou em sua pergunta, então você - como você diz - teria que implementar o cálculo da Distância de Levensthein. Seja no código calculado em cada linha recuperada por um DataReader ou como uma função do SQL Server.

O problema declarado é realmente mais complicado do que pode parecer à primeira vista, porque você não pode presumir saber o que o compartilhado mutuamente elementos entre duas strings podem ser.

Portanto, além de Levensthein Distance, você provavelmente também deseja especificar um número mínimo de caracteres consecutivos que realmente precisam corresponder (para que a similaridade seja concluída).

Em suma:Parece uma abordagem excessivamente complicada e demorada/lenta.

Curiosamente, no SQL Server 2008 você tem a função DIFFERENCE que pode ser usado para algo assim.

Ele avalia o valor fonético de duas strings e calcula a diferença. Não tenho certeza se você fará com que funcione corretamente para expressões com várias palavras, como títulos de filmes, pois não lida bem com espaços ou números e coloca muita ênfase no início da string, mas ainda é um interessante predicado a conhecer.

Se o que você é realmente tentar descrever é algum tipo de recurso de pesquisa, então você deve olhar para os recursos de pesquisa de texto completo do SQL Server 2008. Ele fornece suporte de dicionário de sinônimos, predicados SQL sofisticados e um mecanismo de classificação para "melhores correspondências"

EDIT:Se você deseja eliminar duplicatas, talvez possa pesquisar SSIS Fuzzy Lookup e Fuzzy Group Transformation. Eu não tentei isso sozinho, mas parece uma pista promissora.

EDIT2:Se você não quiser se aprofundar no SSIS e ainda lutar com o desempenho do algoritmo Levensthein Distance, talvez possa tentar esse algoritmo que parece ser menos complexo.