I’m having a similar problem with my VPS, my problem however is rooted in having 2.7 mill categories in my wordpress blog (yes its a CMS) so we’re talking about ‘bad queries’/’bad table structure’ which normally works fine if the tables are small but now have major issues when the tables get larger.
Did you ever find a solution to this problem?