児島です。

> 下記の様に [A] と [B] のトランザクションを並列に実行したところ、
>
>  [A] BEGIN;
>  [B]   BEGIN;
>  [A] SELECT @a:=MAX(id) FROM xx FOR UPDATE;
>  [B]   SELECT @a:=MAX(id) FROM xx FOR UPDATE; /* ロック解放待ち */
>  [A] INSERT INTO xx VALUES(IFNULL(@a,0) + 1); /* デッドロック？ */
>
> [A]のINSERTで以下の通りエラーになりました。
>  ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
>
> たまに発生するとかでは無くて、上の順番で実行すると百発百中で発生します。
> 上記の様な方法で連番を生成する是非はともかくとして、
> デッドロックをしてしまう理由がわかりません。

InnoDB のネクストキーロックによるものだと思います。
試しに、以下のようにトランザクション分離レベルを変更すると
デッドロックはおきませんでした。

  [A] SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
  [B] SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
  [A] BEGIN;
  [B]   BEGIN;
  [A] SELECT @a:=MAX(id) FROM xx FOR UPDATE;
  [B]   SELECT @a:=MAX(id) FROM xx FOR UPDATE; /* ロック解放待ち */
  [A] INSERT INTO xx VALUES(IFNULL(@a,0) + 1); /* 成功 */