The only time I've had corruption issues with mysql is when there's been a violent shutdown, in other words something like an operating system panic or a lockup, which means any pending data hasn't been fully written out to the file system. On reboot the OS fixes up the file system as best as it can but that often does result in a loss of some data, and not always just the stuff that was sitting in RAM waiting to be flushed to disk.
I agree with woj, sounds like your host wasn't really on top of things (assuming they manage your server), unless the corruption has been around for long enough that all of the non corrupt backups have rotated out.
