Sometimes the error message refers to "cmd.exe" even though I am trying to run another executable.

The shell (cmd.exe) is needed to parse the command line in some instances. This is definitely the case when redirection (>, < or |) is used. There may be other cases too.

perl uses environment variable PATH to locate cmd.exe. It should use environment variable COMSPEC to which shell and where it's located, but it doesn't.

Note also that this does not occur if I execute the system command via a perl -e "system(...)"

Maybe cause you didn't turn on warnings, and you had warnings on in your script?

Historic tidbit that may be relevant: Negative return codes didn't use to be valid in DOS. The return value argument of the exit program system call was an unsigned byte. This may have changed in Windows.