This might be a test case for what you are seeing:
CREATE TABLE f611050 (
id INT AUTO_INCREMENT,
user_name VARCHAR(55) NOT NULL,
PRIMARY KEY(id),
UNIQUE(user_name)
) ENGINE=InnoDB;
-- repeat this until if fails to find a row:
BEGIN;
INSERT INTO f611050 (user_name) VALUES (rand());
SELECT @id := LAST_INSERT_ID();
COMMIT;
SELECT * FROM f611050 WHERE id = @id;
However, that is in the same session -- this may or may not be relevant.
If a test like this could demonstrate your problem, please post it in bugs.mysql.com.
If you urgently need a workaround, Session 2 could test for the failure case (no record found) and try again. If Peter is correct about it taking some amount of time for the COMMIT to 'finish', then such a loop would eventually trip over the delay.
Also, the test case should probably have the entire schema that you are using -- there may be an issue relating to how many secondary keys you have.