I encountered this bug on an airline site we wrote and maintain. The site is served from a few machines and a load balancer, we have no appreciable memory issues. As such, I think we can agree it is not a memory problem.
Upgrading from mysql v4.1.10a to v4.1.13 has solved this issue for us. I am fairly certain it is a mysql bug.
As a point of interest, the less you listen to your hosting company about technical issues, the better. They will lie through their teeth to blame their problems on anything but themselves.
HTH
