こんにちは、ひらつかといいます。

> これも削除される行があればデッドロックはしなかったので、
> DELETE文で削除される行がある場合は、その行のみロックされ、
> 削除される行が無い場合はそのテーブル全体へのINSERTがブロックされる
> ような気がするのですが、そういうものなのでしょうか？

削除される行がない場合は、次に存在するレコードまでの値がブロックされる
という挙動になっていると思います。

■接続1
mysql> select * from test;
+----+------+
| id | data |
+----+------+
|  2 | a    |
|  5 | a    |
+----+------+
2 rows in set (0.00 sec)

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> delete from test where id = 3;
Query OK, 0 rows affected (0.00 sec)

■接続2
mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into test values (6, 'b');
Query OK, 1 row affected (0.00 sec) ★成功

mysql> insert into test values (1, 'b');
Query OK, 1 row affected (0.00 sec) ★成功

mysql> insert into test values (4, 'b');
ERROR 1205 (HY000): Lock wait timeout exceeded;
try restarting transaction ★失敗


これはInnoDBのネクストキーロックとギャップロックという仕組みです。

要するに
「id = 3がピンポイントでロックされたという情報を保持する場所が
InnoDBのデータ構造上どこにもないので、【id = 2 と id = 5の間が
ロックされた】と翻訳して、それらのレコードに情報を持たせておこう」
という。

かなり分かりづらいですが、マニュアルにも記載があります。
http://dev.mysql.com/doc/refman/5.1/ja/innodb-next-key-locking.html

また、

・idにindexがあるかどうか
・idがunique keyかnon-unique keyか
・read-committed & binlog_format = rowかどうか

というところで挙動が変わるので、気をつけてください。

間違っていたらすいません。
よろしくお願いします。

-- 
平塚貞夫 hiratsuka.sadao@xxxxxxxxxx