Morning,
I found myself in a very similar predicament. For support and other various reasons, we were unable(unallowed) to install perl on many of our machines out in the field. We purchased perl2exe, and I have been very impressed. I’ve used it to build many executables, and never once had a major problem. When building, it has always included all modules properly. The only downside that I've found is a rather large executable size. You can get perl2exe
here. The Enterprise version is a bit pricey, but well worth it. The evaluation works well, but has a 2 second delay upon program completion. They have it for many different platforms. Hope this helps!
Best Regards,
smack