Se sua string tiver mais de 900 bytes, ela não poderá ser uma chave de índice, independentemente de ser de comprimento variável ou fixo.
Uma ideia seria pelo menos tornar as buscas mais seletivas adicionando uma coluna computada. por exemplo.
CREATE TABLE dbo.Strings
(
-- other columns,
WholeString VARCHAR(4000),
Substring AS (CONVERT(VARCHAR(10), WholeString) PERSISTED
);
CREATE INDEX ss ON dbo.Strings(Substring);
Agora, ao pesquisar uma linha para atualizar, você pode dizer:
WHERE s.Substring = LEFT(@string, 10)
AND s.WholeString = @string;
Isso pelo menos ajudará o otimizador a restringir sua pesquisa às páginas de índice onde a correspondência exata é mais provável de estar. Você pode querer experimentar esse comprimento, pois depende de quantas strings semelhantes você tem e o que melhor ajudará o otimizador a eliminar uma única página. Você também pode experimentar incluir algumas ou todas as outras colunas no
ss index, com ou sem usar o INCLUDE cláusula (se isso é útil variará muito em vários fatores, como o que mais sua consulta de atualização faz, taxa de leitura/gravação etc.). 
