Baron was just writing about problems with the Debian init scripts. The basic problem boils down to /etc/mysql/debian-start running mysqlcheck on every table.
Kolbe Kolbe and Harrison Fisk pointed this out to me last February, and as a result I re-wrote the debian-start.inc script to only operate on MyISAM tables. Additionally, the default config was changed to turn on the myisam-recover option, so even for the MyISAM tables, all we do is touch the table to get MySQL to recover it if needed. (Which I promise you, you really want if you're modifying MyISAM tables on a production server. Don't do that, really, but that's another issue.) The new process essentiall looks like this:
for table in `select TABLE_NAME from information_schema.TABLES where ENGINE='MyISAM'":
select count(*) into @discard from TABLE_NAME
If the table is MyISAM and is not damaged, the select count(*) will be very, very quick and not noticable. If even this is too much, then just remove the myisam-recover entry from your /etc/mysql/my.cnf file, and the debian-start script should be essentially a no-op.
So while I obviously agree with Baron here about the root problem, I'd suggest that rather than disabling the debian-start script, you upgrade to a recent version of it. If it's still a problem, ping me and we can talk about improving the script.