Edite seu arquivo /etc/mysql/my.cnf e certifique-se de alocar memória suficiente para o buffer pool do InnoDB. Se este for um servidor dedicado, você provavelmente poderá usar até 80% da memória do sistema.
# Provide a buffer pool for InnoDB - up to 80% of memory for a dedicated database server
innodb_buffer_pool_size=614M
As chaves primárias são Árvores B, então as inserções sempre levarão tempo O(logN) e quando você ficar sem cache, elas começarão a trocar como loucas. Quando isso acontecer, você provavelmente desejará particionar os dados para manter a velocidade de inserção. Consulte http://dev.mysql.com/doc/refman/ 5.1/en/partitioning.html para obter mais informações sobre particionamento.
Boa sorte!
