Se você pudesse atualizar sua pergunta com o gráfico de deadlock, isso seria uma informação útil. (Quando seu aplicativo encontra um deadlock, o Oracle irá gerar um ORA-00060, e um arquivo de rastreamento será gravado no user_dump_dest.) Se você olhar no arquivo de rastreamento, você encontrará uma seção chamada "Deadlock Graph". Se você puder postar isso, e também postar a declaração que causou o impasse e outras declarações envolvidas no impasse, então podemos começar a tirar algumas conclusões. (Todas as informações que solicitei estão disponíveis no arquivo de rastreamento.)

Como Alessandro mencionou, é possível que sessões bloqueando diferentes linhas na mesma tabela para deadlock devido a chaves estrangeiras não indexadas na tabela filho de um relacionamento pai/filho. Além disso, é possível que você tenha deadlocks em duas sessões atualizando diferentes linhas da mesma tabela, mesmo que a tabela não faça parte de um relacionamento pai/filho, se, por exemplo, a tabela tiver uma escassez de entradas ITL.

Novamente, poste as informações solicitadas acima e tenho certeza de que podemos determinar a causa raiz do seu impasse.

Adicionado em 30/07/2012 **

Adicionando o seguinte, agora que o arquivo de rastreamento de deadlock foi fornecido:Ok, em primeiro lugar, com base no conteúdo do arquivo de rastreamento, este é um deadlock simples devido a sessões sobrepostas/colidindo nas linhas que estão tentando bloquear. Apesar de seus comentários anteriores sobre o impasse estar em diferente linhas, estou aqui para lhe dizer que esse impasse em particular é devido ao bloqueio em nível de linha no mesmo linhas.

O fato de o gráfico de deadlock mostrar o modo em que o bloqueio é mantido é 'X' (exclusivo) e o modo em que o bloqueio é esperado é 'X', me diz que este é um bloqueio simples em nível de linha.

Neste caso, o SID 20 está executando "delete from RPT_TABLE.TEMP_TABLE_T1 where TEMP_T1_ID=:1" e já tem um bloqueio no rowid AAAPDIAAMAAAEfIAAA.

Enquanto isso, o SID 790 está executando "RPT_TABLE.T1_UPDATE_StoredProc", enquanto já mantém um bloqueio no rowid AAAPDIAAMAAAEfGAAA.

Observe na seção "Linhas aguardadas" do arquivo de rastreamento, que o SID 20 está aguardando na linha que o SID 790 mantém e o SID 790 está aguardando na linha que o SID 20 está segurando. Este é um impasse clássico.

Algumas informações adicionais:

• 
  O tipo de enfileiramento é TX (veja o gráfico de deadlock), então definitivamente não bloqueio devido a chaves estrangeiras não indexadas. Se estivesse travando devido a FKs não indexados, o tipo de enfileiramento seria TM, não TX. (Há pelo menos um outro caso em que enfileiramentos de TM estão envolvidos e não são FKs não indexados. Portanto, não assuma que enfileiramento de TM sempre significa FKs não indexados.)
  
• 
  O modo em que o bloqueio está sendo aguardado é 'X' (exclusivo), portanto, este é um bloqueio em nível de linha. Se o modo esperado fosse 'S' (compartilhado), então não ser bloqueio em nível de linha. Em vez disso, pode ser a falta de ITL ou a aplicação do PK ou do Reino Unido.
  

Espero que ajude!