Generally, what you describe as your problem is common windows behaviour.
The startup folder is made for logons.
You have some other possibilities, e.g. I would recommend no. 1.
The most common is, to place, entries in the appropriate registry places:
Google for: "RunOnce"
There are rare scenarios, (hardware scans), where I have seen, RunOnce to be executed before reboot, but for 99,9% percent of all cases this is fine.
Working with scheduled tasks is another possibility. It is not as reliable as the registry keys in my eyes.
The most expensive but only perfect solution is to use the "Run" key with an own tool:
Place your own program there.
And when your program ist called, you can control on your own, if a reboot was done before calling, perform your actions and control, if everything is fine.
Only if it is, you remove yourself of the RUN key. Details maybe not trivial with UAC, so it may be possible to prepare the last task with a scheduled task before.