I can only think of one thing - are you su-ing to root maybe to run this test program? Maybe the fact that your stored and effective uid are different causes problems when you run rsh from perl (which is starting another shell to do it?). Therefore rsh thinks you are someone else and asks you for the password.

You could try my suggestion of running the system() with an array of things in so as not to invoke another shell - this might help. Then again it might be perl doing it...

I always use scp/ssh for this sort of thing and I've never had a problem with it like that. You might need to put a -n on the rsh command line if you run it from a crontab though.