NB: Just a hack as a proof of concept, without taking advantage of the optimization ideas I've already described.

Nevertheless it calculates:

 
====== Calculating base 12
*** Results 18
took: 0 sec

====== Calculating base 14
*** Results 136
took: 0 sec

====== Calculating base 16
*** Results 188
took: 1 sec

====== Calculating base 18
*** Results 7478
took: 5 sec

====== Calculating base 20
*** Results 41984
took: 49 sec
[download]

use strict;
use warnings;
use Data::Dump qw/pp dd/;
use feature 'say';

my $base= 16;
my $verbose = 0 ;


my @digits = 0 .. $base-1;

my %allowed;


@allowed{@digits} = (1)x@digits;

delete $allowed{0};

#pp \%allowed;

our $i;
our $carry;
our $level;
our @factor;
our @product;
our @result;

warn "====== Calculating base $base\n";
my $start =time;

for $i ( reverse 2 .. $base -1 ) {
    delete $allowed{$i} ;
    warn  "=== \$i = $i\n" if $verbose;
    $carry = 0;
    $level=0;

    branch();

    $allowed{$i}=1;
}

say "*** Results ", scalar @result;
say "took: ", time-$start , " sec";


sub branch {
    #say pp \%allowed unless $level;

    local $level = $level+1;

    for my $f ( sort keys %allowed ) {
        my $p = $i *$f + $carry;
        my $digit = $p % $base;
        local $carry = int ($p / $base);

        next if $digit == $f;
        next unless $allowed{$digit};

        unshift @factor,$f;
        unshift @product,$digit
          ;
        warn  " " x $level,
          "Level$level <$f>:  $i * @factor = @product  with <$carry $d
+igit> remain ", (sort keys %allowed) ,
            "\n" if $verbose > 2;

        delete $allowed{$f};
        delete $allowed{$digit};


        if (keys %allowed) {
            branch()
        } elsif (! $carry) {
            warn  "-" x $level, "RESULT Level$level:  $i * @factor = @
+product  with <$carry $digit> remain ", (sort keys %allowed) , "\n" i
+f $verbose >1;
            push @result, [ $i, [@factor], [@product]];
        }

        $allowed{$f} = 1 ;
        $allowed{$digit} = 1 ;

        shift @factor;
        shift @product;
    }
}
[download]

Update: code reformat.