@Rob, you mentioned in here and in your blog entry just now, that the issue only occurs weekdays and from a specific time. Sounds to me then like this is a Cron job, or a backup Daemon of some sort. Something that runs on a schedule. Perhaps locking database tables while it operates. Could even be that a database table has grown larger than the available memory and the engine is no longer properly handling the temp table creations that certain queries would invoke, or maybe an index has corrupted. Could also be that a recent server update has replaced MySQL with MariaDB since modern Linux distributions tend to favour that as a drop-in replacement - there are a few subtle differences in how MariaDB handles certain queries. ORDER clauses on inner queries are ignored if no LIMIT clause is set, for example.
Just throwing ideas out there…