まず再起動前にレジストリ HKCU\Software\Microsoft\Windows\CurrentVersion\RunOnce
の文字列キー(REG_SZ)に自らのプログラムのパスを書き込みます。
そして @MasahikoHirata さんも言っておられる ExitWindowEx を使って再起動(uflags は EWX_REBOOT)します。すると次回起動時に再度プログラムが1度だけ起動するので、続きの処理を行えば良いです。
本来は API を使って RunOnce を書き込みますが、お試しであればコマンドプロンプトから以下を実行して使って下さい。
reg add HKCU\Software\Microsoft\Windows\CurrentVersion\RunOnce /v exec /t REG_SZ /d 実行するプログラム /f
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。