MySQL not respond when overheaded

I have few Drupal 6 websites on webhosting, which causes this strange problem:

• some tables, especially Cache and Watchdog, tend to overhead,
• when overhead is bigger than some amount of kB, MySQL server is refusing connection to given Drupal database or connection is broken during query execution,
• Optimizing table (just overheaded rows) in phpMyAdmin is putting all back to normal.

But - until database is optimized, site is showing just MySQL errors, which is ugly... Where is a problem?

Thank you for any hints I could pass back to the hosting admins!