One thing was forcing InnoDB to cluster by insertion order by adding an otherwise-redundant autoincrement primary key alongside the unique index on the actual key column. Also tweaking various innodb-specific config settings.