sub getEncoding
{
    my ($class, $name, $skip_external) = @_;

    ref($name) && $name->can('renew') and return $name;
    exists $Encoding{$name} and return $Encoding{$name};
    my $lc = lc $name;
    exists $Encoding{$lc} and return $Encoding{$lc};

    my $oc = $class->find_alias($name);
    defined($oc) and return $oc;
    $lc ne $name and $oc = $class->find_alias($lc);
    defined($oc) and return $oc;

    unless ($skip_external)
    {
        if (my $mod = $ExtModule{$name} || $ExtModule{$lc}){
            $mod =~ s,::,/,g ; $mod .= '.pm';
            eval{ require $mod; };    <--- HERE
            exists $Encoding{$name} and return $Encoding{$name};
        }
    }
    return;
}
[download]

it seems that on the line marked with <--- HERE the necessary encodings are loaded at runtime. I don't know about perl2exe, PerlAPP or such, but it will definitely not know what modules your script needs without running it.

Put this at the end of your script:

print STDERR "$_\n" for grep {/Encode/} sort keys %INC;
[download]

and include explicitly any Encode/*.pm files you see. I guess you need to include, Encode/Unicode.pm, so start your script with

use Encode;
use Encode::Unicode;
[download]

_($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                              /\_¯/(q    /
----------------------------  \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}