pp uses
Module::ScanDeps to find all dependencies. This includes all dependencies of your scripts' dependencies.
But you have to be aware of modules that are loaded via code like eval (e.g. eval "require YourModule;"). In that case you have to use the -M option of pp (add a module manually to the archive).
the executable should run on "all" Windows PCs.
Your client/friend should run the executable from DOS-Box, so he gets an error message. That should be helpful.
If you use modules with XS, you may have to add the .dlls with pp's -l (add library) option.
That can be the reason why your exe runs on the PC with ActivePerl (ActivePerl has lots of modules with XS) and not on the other PC.
If you just pack your script, then there is no perl58.dll. It's just an archive with all dependencies (no executable). You have to make an executable...