SELECT ... FOR UPDATE on absent rows

Finally tracked down today at work the source of a year-old bug that was causing (rare) intermittent MySQL deadlocks:

BEGIN;
SELECT i FROM t WHERE i = 42 FOR UPDATE;
(0 rows returned)
[...]
INSERT INTO t SET i = 42;
[deadlock]

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?

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.)