Muita gente acha que é o UPDATE que faz o LOCK, de certa forma é, mas temos que abstrair um pouco mais, e analisar a transação como um todo, não apenas o comando que iniciou o LOCK, o LOCK só será liberado após o COMMIT ou ROLLBACK.
Você deve analisar e identificar qual funcionalidade do sistema que causou o DEADLOCK, e analisar a transação. LOCK/DEADLOCK é gerado pelo mau gerenciamento da transação, ou seja, não está sendo feito o uso do COMMIT/ROLLBACK de forma adequada.