After hours of lost time researching the fix for this, I stumbled across a recent change that was to enable a fix for Speculative Execution.
It was not possible (for me anyway) to roll this fix back, however, I did notice that a single registry key was either missing or of wrong value. As soon as I corrected this value to a string, Hyper-V virtual machines started immediately without any restart.
I got the fix from here https://community.tenable.com/s/article/Speculative-Execution-Side-Channel-Vulnerability-Plugin-and-Mitigation-Information
The key in question is
reg add "HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Virtualization" /v MinVmVersionForCpuBasedMitigations /t REG_SZ /d "1.0" /f