Just one more thing: that works as expected (no deadlock exception) when I am not spamming updates to table. For example:

Transaction 1: Update, no commit.
Transaction 2: Update, (transaction starts waiting).
Transaction 1: Commit;
Transaction 2: (Stops waiting) Commit;

I do not understand when lock happens when I put a much stress to the table.