O InnoDB redefine o campo auto_increment quando você reinicia o banco de dados.

Quando o InnoDB é reiniciado, ele encontra o valor mais alto na coluna e começa a partir daí.

Isso não acontecerá no MyISAM porque ele armazena em cache o último id incrementado.

Atualizar

Esse recurso/bug existe desde 2003 e pode levar a problemas sérios. Veja o exemplo abaixo,

1. 
   A Tabela t1 tem uma chave primária de auto-inc.
   
2. 
   A tabela t2 tem uma coluna para a chave primária em t1 sem uma "restrição" de chave estrangeira. Em outras palavras, quando uma linha é excluída em t1, as linhas correspondentes em t2 ficam órfãs.
   
3. 
   Como sabemos com a reinicialização do InnoDB, um id pode ser reemitido. Portanto, linhas órfãs em t2 podem ser falsamente vinculadas a novas linhas em t1.