There are a couple of solutions, of which the most elegant is to make sure that the directory containing perl.exe is placed in the system path.
I imagine you know how this is done, but for others I'll iterate the process under WinNT 4.0. Start->Settings->Control Panel->System, select the Environment tab, click on System Path in the System Variables box, click in the value box, hit the end key, add ';d:\perl\xxx\bin', replacing that with the fully qualified path to the directory containing the Perl executable, click Set, then OK.
If you're not an administrator on the system, you should be able to add it to the Path variable in the User Environments box. I've never been on a NT system where I'm not an administrator, so I'm not positive.
A more hackish way is look at the Perl variable,
$^X, although you're not guaranteed to get a path in that information. I believe you will under Windows, since argv[0] always contains a fully qualified path name, but you'd have to check that to be sure.
--Chris
e-mail jcwren