Conseguimos achar o problema.
Realmente o problema estava no UPDATE que o trace mostrou. Ficou bem mais fácil achar o problema com um ponto de partida, verificar a transação inteira não era viável.
O Caso do lock de tabela não foi descoberto.
Agradeço a todos pela ajuda
