Seu exemplo em sua pergunta mostra que a ordem de bloqueio depende do método de acesso. Esse caminho de acesso não é decidido diretamente pela cláusula ORDER BY da consulta, existem muitos fatores que podem influenciar esse caminho de acesso. Portanto, você não pode evitar um deadlock apenas adicionando um ORDER BY porque você ainda pode ter dois caminhos de acesso distintos. Na verdade, executando seu caso de teste com a ordem e alterando os parâmetros da sessão, consegui fazer com que duas sessões fossem executadas em um ORA-60 com a mesma consulta.

Se as sessões envolvidas não tiverem outro bloqueio pendente, bloqueando as linhas na mesma ordem em todas as sessões evitará deadlocks, mas como você pode forçar essa ordem de maneira confiável? Observe que isso apenas impediria esse caso muito especial de deadlock de qualquer maneira. Você ainda pode obter impasses com várias consultas em cada sessão ou planos diferentes.

Na prática, este caso é realmente especial e não deve acontecer com frequência:se você está preocupado com deadlocks, ainda acho que existem métodos mais fáceis para evitá-los.

A maneira mais fácil de evitar um impasse é usar FOR UPDATE NOWAIT ou FOR UPDATE WAIT X (embora WAIT X ainda possa acionar um deadlock com valores de X superiores ao mecanismo de detecção de deadlock, atualmente 3 segundos a partir de 11g eu acredito -- obrigado @APC para a correção).

Em outras palavras, ambas as transações devem perguntar:dê-me essas linhas e bloqueie-as, mas se outro usuário já tiver um bloqueio, retorne um erro em vez de esperar indefinidamente. É a espera indefinida que causa impasses.

Na prática, eu diria que a maioria dos aplicativos com usuários reais prefere receber um erro imediatamente do que ter uma transação esperando indefinidamente até que outra transação termine. Eu consideraria FOR UPDATE sem NOWAIT apenas para trabalhos em lote não críticos.