Hi Botho,
Please have a look at the following documentation:
Troubleshoot Start/Stop VMs during off-hours issues
https://learn.microsoft.com/en-us/azure/automation/troubleshoot/start-stop-vm
Scenario: All VMs fail to start or stop
Scenario: Some of my VMs fail to start or stop
Hope some of the scenarios in the documentation help. I'd also recommend taking a look at your Azure activity log to see what the exact error is:
https://learn.microsoft.com/en-us/azure/azure-monitor/essentials/activity-log?tabs=powershell
If this is helpful please accept answer.