I suggest that you should carefully explore and then address these client objections, such as "But he wants to avoid third party installations." And then, in turn, to address the subsequent objections that he might presume to be the case: "would not allow the installation of the Perl interpreter under a privileged account."
The client's justifiable concerns for security could in fact be addressed by implementing, within that "privileged account," an entirely self-contained and isolated Perl installation which could, nonetheless, "avail itself of libraries in the conventional way" because the search-scope could be constrained and predicted.
I would argue that it isn't actually necessary to "build an EXE," and, given the client's expressed concern for adequately covering seven years' worth of Windows versions, you probably couldn't cover the requirement that way if you tried. Your solution, when deployed into any of the client's various target environments, needs to be provably adaptable to each and every one of them.
Therefore: "perhaps, a custom-compiled Perl executable, with a strictly-specified default library search path." Then, an execution environment sufficiently regulated to guarantee that this perl-command will be the one that is selected. Beyond this, absolute control over PERL5LIB at runtime, and the cpan library search paths for any updates.
In short, "to my way of thinking, the existing features of Perl should be able to serve both you and your client very well, in his privileged environment, so long as you are able to guarantee Ц as you can do Ц what it "sees." Importantly, you should be able to devise a situation that is fully and automatically adaptable between Windows versions. (Which a rigid, EXE-based strategy probably could not do.)