auto_increment incremented on non-affecting queries
This shouldn't be right, should it?


It's right.

Databases (not just MySQL) generally ensure that sequences will only ever increase (once a transaction is committed), but not that they will be without gaps. For instance, TFM says:


  You may see gaps in the sequence of values assigned to the AUTO_INCREMENT column if you roll back transactions that have generated numbers using the counter.


and:


  As of MySQL 5.1.22, InnoDB can avoid using the table-level AUTO-INC lock for a class of INSERT statements where the number of rows is known in advance, and still preserve deterministic execution and safety for statement-based replication. Further, if you are not using the binary log to replay SQL statements as part of recovery or replication, you can entirely eliminate use of the table-level AUTO-INC lock for even greater concurrency and performance, at the cost of permitting gaps in auto-increment numbers assigned by a statement and potentially having the numbers assigned by concurrently executing statements interleaved. 


Consider the case where two uncommitted transactions exist in an MVCC system like InnoDB. They may both need a unique primary key before being committed, but the first transaction may fail. Hence you will end up with a gap.

You can't avoid this behaviour, so embrace your gappy primary keys :)

https://dev.mysql.com/doc/refman/5.1/en/innodb-auto-increment-handling.html