One thing which struck me as odd when I started working here is that we used moderately long strings, called 'pids' as primary keys on many of our tables. These keys are char(8) and encoded as utf8. This makes the key length longer than it needs to be and longer primary keys can cause performance issues (which is why you rarely see UUIDs being used as primary keys).
When I asked about this, I was informed about a "fun" issue with MySQL. Apparently, when using InnoDB (we have MySQL version 5.0.45), AUTO_INCREMENT keys lock the entire table and we were getting serious deadlock issues. Allegedly this is fixed in 5.1. The rationale listed?
[Table level locks are] necessary with the current logical binlogging of MySQL, since the auto-inc values assigned in a single SQL statement must be consecutive.
I don't understand this. From an application standpoint, auto-inc keys should be non-identifying and frankly, it shouldn't matter if they're consecutive, ordered, random, whatever, so long as they're unique. I suspect that this is done for internal architectural reasons because I can't imagine that even the MySQL developers think that it's logically necessary that these keys be consecutive.
The counter-argument I envision is someone telling me that you want to know what order the records were inserted in and gaps will give you an idea of what you might be deleting. If that's the counter-argument, I would suggest that you explicitly plan for this and not rely allow an internal implementation detail. That's encapsulation violation.