We have a customer using a cheap managed hosting provider, and their MySQL server very aggressively times out and drops the connection.
I wonder if this could be causing us troubles as outlined here: Massive template cache cleaning tasks always get stuck
Does Craft attempt to reconnect to MySQL if the connection drops halway through a request?