Se as strings com as quais você está trabalhando são tão simples quanto a entrada e a saída da amostra, eu diria que você está tornando isso mais difícil do que é. Você pode apenas procurar por "john)" e "james", assim:
$ echo "this is 1(the house owner 2(pet-name john) john and his friend 3(unknown name james) james fred)" | sed -r 's/(john\)|james\))/xxx-/g'
this is 1(the house owner 2(pet-name xxx-john) john and his friend 3(unknown name xxx-james) james fred)
Desde que você mencionou padrões não-gananciosos, tenho a sensação de que há mais nisso do que seu exemplo mostra. Então, vamos fingir que não sabemos se haverá um parêntese de fechamento logo após os nomes:
$ echo "this is 1(the house owner 2(pet-name john ok) john and his friend 3(unknown name james test) james fred)" | sed -r 's/(\([^()]*)(john|james)([^()]*\))/xxx-/g'
this is 1(the house owner 2(pet-name xxx-john ok) john and his friend 3(unknown name xxx-james test) james fred)
O primeiro conjunto de parênteses captura tudo após (e incluindo) um parêntese de abertura literal que não é um parêntese de abertura ou fechamento até que ele atinja "james" ou "john".
O segundo conjunto de parênteses captura "john" ou "james".
O terceiro conjunto de parênteses captura qualquer coisa depois de "james" ou "john" que não seja um parêntese de abertura ou fechamento até atingir um parêntese de fechamento literal.
Este é um substituto global, por isso vai funcionar, não importa quantos conjuntos de parênteses você tenha. Você pode até aninhá-los mais profundamente, e isso só se aplica ao menor conjunto.
A ganância não entra em jogo nesta situação, mas se for para o projeto em que você está trabalhando, basta adicionar um ponto de interrogação (por exemplo, * se torna *?) para torná-lo não-voraz.