Virtual Machine could not be started because the hypervisor is not running

January's Patch Tuesday (11th January 2022) has featured two updates that appear to break Hyper-V on Windows Server 2012 R2 servers. If you installed either KB5009624 or KB5009595 and are receiving "Virtual Machine {VM NAME} could not be started because the hypervisor is not running" then you should uninstall both updates and restart.

The following events will also be visible in the System Event Logs:

Source: Hyper-V-Hypervisor
Error ID: 80
Hypervisor launch failed; The operating systems boot loader failed with error 0xC00000BB.

Source: Hyper-V-VMMS
Error ID: 15350
The virtualization infrastructure driver (VID) is not running.

Source: Hyper-V-VMMS
Error ID: 15160
'MACHINE NAME' failed to restore virtual machine state.

Workaround

There is no permanent fix currently available. To restore the stopped Virtual Machines you should uninstall the update from the Hyper-V host by doing the following:

1) Open elevated command prompt on the Hyper-V Host
2) Run "wusa /uninstall /kb:5009624"
3) Run "wusa /uninstall /kb:5009595"
4) Restart the Hyper-V Host

Fix (Updated 18/01/2022)

Microsoft have now released KB5010794, an Out of Band (OOB) update, to resolve these issues. This update won't be pulled down by Windows Update and can only be retrieved from the Microsoft Update Catalog. This update is only 81MB compared to the 550MB in KB5009624, and so it would seem that you must reinstall KB5009624 before installing KB5010794.

The steps below assume you have already installed KB5009624 and are experiencing the issues above:

1) Visit the Microsoft Update Catalog (this is important, the update won't pull down using Windows Update)
2) Download the correct update package for your OS
3) Double click the .MSU file and follow the steps
4) After it has installed restart the server

Update (14/01/2022) - Microsoft have now publicly acknowledged the issues at Windows 8.1 and Windows Server 2012 R2 | Microsoft Docs. Still no fix yet.