I am filing this bug with MariaDB, just for the sake of completeness, as it was already filed with MySQL/InnoDB here (by someone else):

http://bugs.mysql.com/bug.php?id=76872

"InnoDB AUTO_INCREMENT produces same value twice"

"When more than one INSERT is executed concurrently on a non-empty InnoDB table with an AUTO_INCREMENT PK immediately after MySQL start up (before any other INSERTs on the same table) one will often fail with the message like "Duplicate entry '123' for key 'PRIMARY'". This will only happen if innodb_autoinc_lock_mode is 1 or 2 and auto_increment_increment > 1."

There is much more in the actual bug report, but I didn't want to copy/paste the entire report.