Auto Increment Primary ID inserting random values
I'm having a very difficult time thinking of any possible misbehaving mechanism inside MySQL or InnoDB that could cause this behavior as the result of a bug, without throwing errors or causing a crash.  It seems much more likely that the table is being updated by the application.  Instead of writing new rows, something is finding and updating old ones.

If that's not supposed to be happening, I would put a trigger on this table to block those updates.

mysql&gt; CREATE TRIGGER txn_bu BEFORE UPDATE ON txn FOR EACH ROW 
       SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = 'this table does not support updates';
Query OK, 0 rows affected (0.14 sec)

mysql&gt; UPDATE txn SET `timestamp` = NOW() WHERE id = 1;
ERROR 1644 (45000): this table does not support updates

mysql&gt;


This makes directly updating rows impossible.  Note that you don't need the usual DELIMITER change and BEGIN/END blocks because the trigger is comprised of a single simple statement.

If the table is never updated then the trigger would never fire, so there's no significant overhead associated with having it defined.  If it sees an update query then it's going to throw an exception back to the application which should generate exception reports or support tickets.  Arguably, if your application has a defect that's stomping data, you want it to fail hard, instead of soft.