MySQL memory problems: "Unable to save result set"

I recently developed a Drupal site for a client and then uploaded it to their host, and everything seemed ok.
All the sudden I got few error from completely random nodes saying:

mysql_query() [function.mysql-query]: Unable to save result set on file /includes/database.mysql.inc line 153.

I tried repairing the tables from phpmyadmin interface, but that didn't go through allright.. after that I got several errors like these:
Got error 12 from storage engine query which seems to mean error in memory allocation.

Repairing the tables failed several times due to not having enough memory for the action - and when I finally got them repaired, the original error came back couple hours later, so still getting those "Unable to save result set" errors every couple of hours.

I _hope_ this is strictly a server issue that the hosting company should solve, but of course some coding error can always be the cause - any ideas? I can't reproduce this error, which makes it hard to debug it.