I went back and forth with them about optimizing the app, but it was apparently some huge labyrinthine monstrosity. They insisted that they didn't have the resources to do any of the significant rewrites that it would require to fix the app to do proper queries (or at least, not enough to be worthwhile).
Eventually I gave up. /tmp was mounted onto a separate partition, so I disabled ext3 journalling and set commit=30 so that it only sync'ed to the disk every 30 seconds. Since no temporary tables lasted that long, the VFS layer never wrote to the disk if it didn't have to. /tmp became an in-memory cache, and CPU use dropped to 5%.
Optimizing isn't about a checklist, it's about looking at the system that you have, understanding what it's doing and why, and understanding how the other systems around it behave so that you can resolve the issue. Moving onto another database server wouldn't have helped them. Moving onto a RAID would have reduced the impact, but their load didn't scale linearly so they'd hit their limit in a few months anyway.
In all of my cases dealing with scale issues it's been due to the DB growing very large in size to the point where you can't use the same techniques that you're used to using. That usually happens in combination with more concurrent users. Depending on how large and how organized your code is, things can get very ugly when the site starts throwing errors, being unresponsive, etc.
I usually know where I want to go as a next step with scaling and monitor our resource usage until it gets pretty high. Then we take the next step. But we don't spend a huge amount of time scaling until we know we need it.