G'day Limbic~Region,

Here's my take on a solution. It uses the 2of12inf.txt dictionary. It takes about a minute to run on my OS. [as always, YMMV] It doesn't use any particularly noticeable amounts of memory.

#!/usr/bin/env perl

use 5.010;
use strict;
use warnings;
use autodie;

die "Usage: $0 dictionary max_letters min_letters\n" unless @ARGV >= 2
+;
my ($DICT, $MAX, $MIN) = @ARGV;
$MIN //= 1;
my %dict_extract;

open my $fh, '<', $DICT;
while (<$fh>) {
    s/%?\r?\n?$//;
    next if length > $MAX;
    ++$dict_extract{+length}{join '' => sort split ''};
}
close $fh;

my $best_letters = '';
my $most_words = 0;

for my $letters (keys %{$dict_extract{$MAX}}) {
    my $count = get_count($letters, {});

    if ($most_words < $count) {
        $most_words = $count;
        $best_letters = $letters;
    }
}

say "Best: $best_letters - Count: $most_words";

sub get_count {
    my ($letters, $counted) = @_;

    return 0 if $counted->{$letters}++;

    my $len = length $letters;
    my $count = $dict_extract{$len}{$letters} // 0;

    if ($len > $MIN) {
        $count += get_count($_, $counted) for map {
            my @sub_string = split '', $letters;
            splice @sub_string, $_, 1;
            join '' => @sub_string;
        } 0 .. $len - 1;
    }

    return $count;
}
[download]

Output:

Best: aeinprst - Count: 346
[download]

I also wrote a complementary script to check the results (this only takes a second or two to run):

#!/usr/bin/env perl

use 5.010;
use strict;
use warnings;
use autodie;

die "Usage: $0 dictionary solution max_letters\n" unless @ARGV == 3;
my ($DICT, $SOLUTION, $MAX) = @ARGV;

my $count = 0;

open my $fh, '<', $DICT;
while (<$fh>) {
    s/%?\r?\n?$//;
    next if length > $MAX;

    if (matching_word($_)) {
        ++$count;
        say;
    }
}
close $fh;

say "Total: $count";

sub matching_word {
    state $solution_letters = [ split '' => $SOLUTION ];

    my ($word) = @_;

    foreach my $letter (@$solution_letters) {
        my $pos = index $word, $letter;

        if ($pos != -1) {
            substr($word, $pos, 1) = '';
            return 1 if length $word == 0;
        }
    }

    return 0;
}
[download]

Output:

air
airs
an
...
tripes
trips
tsar
Total: 346
[download]