Actually, with "pp --perlscript" (aka "pp -P"), you will not need PAR installed on those machines -- they just need to have the correct version of Perl installed.

It is not possible to produce a .exe file runnable on Win32, while at same time being a valid Linux binary, as you suggests. At least, I don't know how -- suggestions welcome.