Você pode usar um loop. O seguinte removeria \index{foo} desde que seja precedido por um limite de palavras.
sed -r ':a;s/\b\index\{[^{}]+}//;ta' inputfile
Para sua amostra, ele produziria:
\index{Testing One Two Three}
No entanto, esteja avisado sobre o uso de expressões regulares para analisar e manipular esses padrões aninhados. Caso isso aconteça, certifique-se de observar o diff da entrada antes e depois da alteração.
EDIT: Explicação:
Veja primeiro o comando de substituição:
s/\b\index\{[^{}]+}//g
-
\bcorresponde a um limite entre um caractere de palavra\we um caractere não de palavra\W. -
\index\{corresponde a\index{ -
[^{}]+}corresponde a um ou mais de qualquer coisa que não seja}seguido por}
:a é um rótulo. ta ramifica para rotular a se a substituição foi bem sucedida.
Portanto, funcionaria removendo o mais interno index{} da string, de tal forma que
\index{Test\index{test\index{test}}ing One\index{one} Two\index{two} Three\index{three}}
se transformaria em:
\index{Test\index{test}ing One\index{one} Two\index{two} Three\index{three}}
e assim por diante até a substituição falhar.