I've had load issues in Postgres, not MySQL before and it was due to autovacuum running on tables getting updated/inserted frequently. I'm not sure what the equivalent in MySQL is, but if you have a ton of insert/update queries, consider archiving your tables after a certain period of time, so that your main table doesn't have ton of rows. You can consider sharding of course, but also consider sharding the actual tables in the same database. An insert query on a table with 1000 rows will take much much less time than an insert query on a table with 100 million rows, all things considered.

Also, consider creating a buffer in the application layer that buffers inserts/updates and executes them once as a single transaction, if they don't need to be executed immediately. It puts less stress on the database. Of course, this would require a lot of rewriting in your app, so not sure if you want to go through this route.

Indices are another area. I'm sure plenty of people have told you to optimize your indices, but also consider REMOVING unnecessary indices. Do you have an index on a text column, or multiple varchar columns? Those can be killer after awhile because inserts will slow down. Consider changing indices on varchar columns to indices on an int column by hashing those strings.

A quick suggestion: Install NewRelic (it's free for a certain period), and check out the database transactions that are taking up the most CPU load. Sometimes there's that 1 query you overlooked that is table scanning and could be the main culprit.

Also, are you using Rails by any chance? If so, there are other areas I can suggest.

And please post your server specs. Maybe your VPS just does suck (no offense), and the easiest route is just to upgrade your server.