Moin,
eine Möglichkeit wäre, dass es tatsächlich an dem Debian-Paket liegt. Die Debian-MySQL-Pakete sind ein bissl berüchtigt dafür, nicht gerade für stark ausgelastete Server optimiert zu sein (siehe http://www.rootforum.org/forum/viewtopic.php?p=240232).
Habt Ihr mal mit MyTop analysiert, was der Server denn gerade tut, wenn die Last so exorbitant hoch ist?