MySQL seems to hang the server

I run nginx + passenger (for Rails) on my server and no changes has been made recently to cause any trouble, nor I had any unusual traffic.

The problem is this: the server simply does not respond to anything, nor http neither ssh. I have only managed to reboot it in Linode Manager, but it hangs again after a few minutes if nginx is working. I checked and there seemed to be a high IO spikes today. After they happened the problem became noticeable.

I started digging and found that the server un-hangs after a couple of minutes and 500 error is displayed on all pages. Restarting mysql seems to help, but it hangs again later.

There's enough space on the disk and there's enough memory and apart from mysql saying

* Checking for corrupt, not cleanly closed and upgrade needing tables.

everything seems to be normal. This MySQL error does not seem to have any implication on my applications data. I checked all the tables with mysqlcheck, no errors were found. Any ideas?