Thank you for your thoughts:
I have now added the full path to rsh as suggested. It does not appear to have changed anything.
I'm still looking at the shell quoting idea.
Yes, I can run the rsh stuff from the command line on the w2k box just fine. Its only when I try and do it from the perl that things go wrong!