Run schedule task before windows service starts

You could run it silently using a Windows Script file instead. The Run Method allows you running a script in invisible mode. Create a .vbs file like this one

Dim WinScriptHost
Set WinScriptHost = CreateObject("WScript.Shell")
WinScriptHost.Run Chr(34) & "C:\Scheduled Jobs\mybat.bat" & Chr(34), 0
Set WinScriptHost = Nothing

and schedule it. The second argument in this example sets the window style. 0 means "hide the window."

Complete syntax of the Run method:

 object.Run(strCommand, [intWindowStyle], [bWaitOnReturn])

Arguments:

• object: WshShell object.
• strCommand: String value indicating the command line you want to run. You must include any parameters you want to pass to the executable file.
• intWindowStyle: Optional. Integer value indicating the appearance of the program's window. Note that not all programs make use of this information.
• bWaitOnReturn: Optional. Boolean value indicating whether the script should wait for the program to finish executing before continuing to the next statement in your script. If set to true, script execution halts until the program finishes, and Run returns any error code returned by the program. If set to false (the default), the Run method returns immediately after starting the program, automatically returning 0 (not to be interpreted as an error code).

Yes, this service will run after reboot, you can verify it in the Task Scheduler service transaction log:

    Systemroot\SchedLgU.txt
   
    (where Systemroot is your windows installation folder)

If it's not working correctly (under XP, unsure about 2008 equivalent):

    
    Control Panel -> Administrative Tools -> Services -> Task Scheduler 

    Set to auto. 

2008 Documentation here, XP Documentation here

The task's schedule commences at the specified time, after that it executes based on the repetition parameters. The start time can be considered as "task installation" time, it is not part of the repetition parameters (except as a timer offset). Hope that makes sense!