Start with "Resultant Set of Policy" (
rsop.msc) and see if the GPO containing your script is being processed. Most often, I find, problems with policy application end up being a discrepancy between the sysadmin's understanding of where to link a GPO and how the list of GPOs that apply to a given user or computer are actually calculated by the OS.
If the GPO is being processed but the script isn't executing I'd check to see that the permissions set on the script allow the computer account of the subject computer to read / execute the script and that the path referenced in the GPO resolves properly on the subject computer.
You're looking in the wrong place in the Resultant Set of Policy tool. "Software Settings" is the place in Group Policy where software can be "force" installed. You're interested in "Computer Settings / Windows Settings / Scripts (Startup/Shutdown)".
I'd be most interested to see if the GPO where you've specified the script is listed on the "General" tab of the "Properties" of the "Computer Settings" node in RSoP. I suspect that you're going to find that the GPO isn't listed there and, as such, isn't being processed.
Where did you link the GPO you created that specifies the Startup Script?
So, you're seeing your script's path under the "Scripts (Startup/Shutdown)" node in RSoP. You should have an "Last Executed" column there. If there's a date / time listed there then the Group Policy client has attempted to execute your script. If there's no time listed then it hasn't attempted to execute it.
Hopefully you've looked at the Application Event Log and verified that there aren't any errors being logged re: executing the script. If you haven't, look there.
Assuming the script is being executed I'd consider adding a line to leave some kind of "mark" on the computer to positively verify that the script is executing. Something like an
echo foo > %TEMP%\foo.txt would give you a file in the system-wide %TEMP% directory (typically "C:\WINDOWS\TEMP") that could tell you, conclusively, if the script is executing. I'm beginning to suspect that your script is executing but that the computer's SYSTEM context isn't able to access the EXE's you're trying to execute for some reason.