Re: "Lock wait timeout exceeded" time out on insert.
Suggest you turn on the "general log" until the problem occurs again (or you run out of disk space!). Then look near the end of the log for the two connections that collided. Be sure to look far enough back in the general log to get anything that in each of the two "transactions".
I want to particularly see that either autocommit is ON or all the SQL statements (in a connection) between the BEGIN and the COMMIT.
Study
http://dev.mysql.com/doc/refman/5.0/en/innodb-locking-reads.html
"Locking of rows for update using SELECT FOR UPDATE only applies when autocommit is disabled (either by beginning transaction with START TRANSACTION or by setting autocommit to 0. If autocommit is enabled, the rows matching the specification are not locked. "
http://dev.mysql.com/doc/refman/5.0/en/commit.html
"After disabling autocommit mode by setting the autocommit variable to zero, changes to transaction-safe tables (such as those for InnoDB, BDB, or NDBCLUSTER) are not made permanent immediately. You must use COMMIT to store your changes to disk or ROLLBACK to ignore the changes."
"To disable autocommit mode for a single series of statements, use the START TRANSACTION statement"
You are using Java, correct? Well, JDBC may be throwing things in that you don't realize. (The general log would spot them.) --
"Many APIs used for writing MySQL client applications (such as JDBC) provide their own methods for starting transactions that can (and sometimes should) be used instead of sending a START TRANSACTION statement from the client. See Chapter 19, Connectors and APIs, or the documentation for your API, for more information. "
(I have seen lots of extra commands put in by JDBC, but I don't have any details handy.)
> This insert is not in a big transaction, but it is in a simple one.
It doesn't take a complex transaction to hit a deadlock.
> Also, there is not that much else happening on the database.
All it takes is one other statement -- of the right type.