even with innodb you will still find yourself running optimize.
checkout what wordpress does (from wp-content/plugins/akismet/akismet.php):
if ( (mt_rand(1, 10) == 3) ) {
// WP 2.0: run this one time in ten
akismet_delete_old();
}
and then in that function, after the DELETE, is this:
$wpdb->query("OPTIMIZE TABLE $wpdb->comments");
I am sure there are plenty of people out there having fun trying to work out why there tables suddenly lock and they see an optimize process running randomly. I am also sure it runs fine in their unit tests when they have 1 post and 2 comments.
all this because they DELETE :) They have all comments, those that have been approved, those that are in moderation, and all spam, in the same table - so if they don't delete the table would become unmanagable, so it is the design at fault and the wrong solution. If you search source at github or somewhere similar, you will find projects with OPTIMIZE everywhere - solving a real problem entirely the wrong way
I got used to it because the advantages just far outweigh the disadvantages. Records don't disappear for malicious reasons or because of mistakes - you can purge records marked delete every 30 days with a background process, if you like - but I no longer, ever, type that keyword into an app.