Ответ на загадку
Проблема в том, что в InnoDB уровень изоляции по умолчанию REPEATABLE READ. Если две транзакции одновременно сделают селект фор апдейт по одному и тому же предикату, а такой записи не будет, то первая транзакция, которая попытается вставить эту запись, будет заблокирована, так как другой транзакции уже было обещано, что такой записи нет, и никто на нее блокировку не поставит. Вторая же транзакция потом тоже захочет сделать такой же инсерт и тут уже она будет заблокирована инсертом первой транзакции. Па-бам, у нас дедлок на ровном месте!
Лечится понижением уровня изоляции до READ COMMITTED. Плюс надо починить логику самого метода — добавить двойной чек с синхронизацией, чтобы параллельные транзакции не хотели одновременно добавить одну и ту же запись ни при каких условиях. При понижении изоляции дедлока уже не будет, но одна транзакция может закончиться с ошибкой дубликата первичного ключа, если не сделать такую синхронизацию.
