This is due to the Fast Startup Windows 10 feature.
On "Shutdown", by default, Windows 10 actually hibernates the kernel. And then the "cold boot" is actually a resume from kernel-only hibernation. Counterintuitively, "Restart" leads to the the actual cold boot.
Instead of disabling hibernation you can trigger the task on the "resume from hibernation" event:
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/qi3eJ.png)
For some reason I had to go through the "Custom" option for the task to trigger correctly. So here's the trigger in XML in case something doesn't work:
<EventTrigger>
<Enabled>true</Enabled>
<Subscription><QueryList><Query Id="0" Path="System"><Select Path="System">*[System[Provider[@Name='Microsoft-Windows-Power-Troubleshooter'] and EventID=1]]</Select></Query></QueryList></Subscription>
</EventTrigger>
Microsoft Community thread:
Scheduled "At Startup" task that worked in Windows 7 no longer works after upgrade to Windows 10