There is this note in the pp documentation that kinda kills the usage of PAR/pp on systems without Perl installed:

Note that if your perl was built with a shared library, the 'Stand-alone setup' above will still need a separate perl5x.dll or libperl.so to function correctly. Patches to include a copy of libperl with the executable are most welcome.

I've had luck with Perl2Exe for smaller applications. (or pointers to a static linked win32 version of Perl 5.6.1)