Concurrency и паттерны ошибок, скрытые в коде: Deadlock

wound/wait mutex?

Теперь немного о том, как это исправить

Да ну нафиг.
Как минимум, непонятны ожидания от StartUpdate — иногда он блокирует поток, иногда нет. В идеале, нужно сделать так, что если CheckAndUpdate ещё не стартовал, то StartUpdate ничего не делает.

Но вообще непонятно, что защищает m_mutex. В Future уже есть синхронизация, в этом рафинированном примере m_mutex не нужен.