I tried Muskrat's solution of PAR (particularly the pp packager). It works! Note that the installation process is a bit of a bear and the executable files are big (800k exe for a 2k script) if you're going to try something like this on your own.
Thanks again Muskrat.
Comment on Re: Distributing or Sharing Perl Scripts
One thing about PAR is that you still have to put perl58.dll on each machine (assuming you are using the most recent version of ActivePerl). It can be in the same directory as the exe file. I also know that it can be UPX-ed down to about 360k vs 750k. Unfortunately UPX doesn't work on the exe file created by PAR