Suas duas instruções adquirem bloqueios de linha em ordem diferente. Esse é um caso clássico para impasses. Você pode corrigir isso garantindo que a ordem dos bloqueios seja sempre em alguma ordem global (por exemplo, ordenada por ID). Você provavelmente deve unir os dois UPDATE instruções em uma e classifique a lista de IDs no cliente antes de enviá-la ao SQL Server. Para muitos UPDATE típicos planeja isso realmente funciona bem (não garantido, no entanto).

Ou você adiciona lógica de repetição caso detecte um impasse (SqlException.Number == 1205 ). Isso é mais elegante porque não requer alterações de código mais profundas. Mas os deadlocks têm implicações de desempenho, portanto, faça isso apenas para baixas taxas de deadlock.

Se o seu processamento paralelo gerar muitas atualizações, você pode INSERT todas essas atualizações em uma tabela temporária (que pode ser feita simultaneamente) e quando terminar você executa um grande UPDATE que copia todos os registros de atualização individuais para a tabela principal. Você acabou de alterar a fonte de junção em suas consultas de amostra.