Se você estiver usando o InnoDB ou qualquer RDBMS transacional em nível de linha, é possível que qualquer write transação pode causar um deadlock, mesmo em situações perfeitamente normais. Tabelas maiores, gravações maiores e blocos de transação longos geralmente aumentam a probabilidade de ocorrência de deadlocks. Na sua situação, provavelmente é uma combinação destes.

A única maneira de realmente lidar com deadlocks é escrever seu código para esperá-los. Isso geralmente não é muito difícil se o código do banco de dados estiver bem escrito. Muitas vezes você pode simplesmente colocar um try/catch em torno da lógica de execução da consulta e procure um deadlock quando ocorrerem erros. Se você pegar um, o normal é tentar executar a consulta com falha novamente.

Eu recomendo que você leia esta página no manual do MySQL. Ele tem uma lista de coisas a fazer para ajudar a lidar com impasses e reduzir sua frequência.