using rsh to run a program on a remote system is awkward because the user shell is run in nonlogin, noninteractive mode, which means it never executes /etc/profile which usually means the $PATH variable is not set up. Interesting enough it runs just fine when rsh is used to simply bring up an intereactive shell. First observed when running between two machines, but problem can be demonstrated on single machine by rshing to itself. rsh localhost brings up a shell that has everything setup properly. rsh localhost "echo $PATH" shows only the default user/bin:/bin path. I have worked around this by having the /etc/bashrc script invoke the /etc/profile script if it hasn't been run yet. But that really shouldn't be necessary.
This is actually a bash (started up by rsh) problem. The behavior is annoying, but well known (and well documented).
This is actually the standard behavior of rsh (rshd). If given a command, rsh(d) executes the command directly, without running a login shell. If not given a command, rsh reverts to rlogin(d), which in turn runs a login shell which, for bash, runs /etc/profile and ~/.bash_profile.