Is it possible that the LocalSystem account is not inheriting the PATH variable, and not finding the program ?
Have you tried it with a fully qualified path to "mycmd" ?
To get a feel for what the environment is, change your code to run "cmd /k" without redirection. Also, you need to setup your service to "allow interaction with the desktop". Then you can see what rights are available to the command prompt.

"When you are faced with a dilemma, might as well make dilemmanade. "