BEGIN;Huh? How can this deadlock -- didn't I just get a write lock before? If not on the record itself (which didn't exist), then at least on the gap where it would be inserted, right?
SELECT i FROM t WHERE i = 42 FOR UPDATE;
(0 rows returned)
INSERT INTO t SET i = 42;
Turns out that MySQL/InnoDB doesn't acquire an exclusive lock in this case. It will get a shared lock (on something), though, preventing any concurrent INSERT for that row, but making it possible to deadlock when INSERT requests the proper exclusive lock it requires. Hilarity ensues.
(Despite comments to the contrary in the bug report, I can reproduce this for any value, large or small.)
(Update: This apparently varies from one DBMS to another.)