Why does the delete/update block each other in this case?
Answer based on comments by a-horse-with-no-name
You are probably being hit by MySQL's &quot;gap locking&quot; (locking rows that aren't there).

https://dev.mysql.com/doc/refman/5.6/en/innodb-locking.html#innodb-gap-locks

Gap locking is not needed for statements that lock rows using a unique index to search for a unique row. (This does not include the case that the search condition includes only some columns of a multiple-column unique index; in that case, gap locking does occur.)


https://www.percona.com/blog/2012/03/27/innodbs-gap-locks/

MySQL uses REPEATABLE READ as the default isolation level so it needs to lock the index records and the gaps to avoid phantom reads and to get a consistent Statement based replication. If your application can deal with phantom reads and your binary log is in row format, changing the ISOLATION to READ COMMITTED will help you to avoid all those extra locks.