I've encountered similar difficulties (which ultimately led me back to perl2exe). My observations were that PAR tends to "run amok" when it resolves dependent modules, and pulls in a lot of extra stuff you probably don't need. In my case (a fairly large scale ptk app), the PAR archive file was >10Megs, while the perl2exe was about 6 megs. Initial bootup times for PAR were completely unacceptable; perl2exe is pretty reasonable (and it opens a ptk splash screen much quicker as well.) Even after the initial bootup, the PAR boot time was much greater than perl2exe.

Another PAR downside (IMHO) is the reliance on the temp directory structure; once people suss out their temp directories, they've got to endure the long load again.

PAR could mitigate some of this by providing a splash screen hook, but thus far that feature seems to be low priority. While I appreciate the PAR toolset (esp for supporting more exotic platforms), I'd recommend perl2exe if you're running on a mainstream platform (Win32, Linux, Solaris).