I was watching the mysql queries using mytop just before our server went down. In a flash I realized the cause of our persistent server load problem. I have also come up with an elegant solution which I will implement in the next few days.

The problem is due to huge spam comment load on my server and the facts that a) MySQL does table locking on insert and b) update statements gets priority over the select statements. So if you have even one "insert into wp_comments" waiting (due to table locking) then all the "select from wp_comments" are forced to wait in queue.

What about the solution?
There are few obvious ways to handle it. The first thing I tried is setting updates to low priority to allow select statements to pass through:
set-variable = low_priority_updates=1
In WordPress updates are much less frequent than reads, so it makes sense to give lower priority to updates and let select pass through.

So far everything looks great. Keep an eye on this article to get updates on my quest.