It sounds to my like the issue might be in your %PATH%, but cmd.exe really should be in C:\WINNT\system32\, which ought to be in your PATH. Try 'set PATH' to check this.
>> I need to use the batch file because the program it's
>> running assumes /program files/agent is the working dir
so if you added a 'chdir' call to your perl you could avoid the batch file? I'd probably try to do that, if it was my code...