Ah! So, a final check is required to eliminate words that use too many of any given letter. Could probably be achieved more efficiently, but since it's only run on a very short list and short circuits...

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

sub finalCheck{
    my( $poss,  $given ) = @_;
    $given =~ s[$_][] or return for split '', $poss;
    return 1;
}
sub uniq{ my %x; @x{@_} = (); keys %x }

my @words = do{ local *ARGV = ['words.txt']; <> };
chomp @words;

@words = grep length() > 2, @words;

my %index;

@index{ 'a' .. 'z' } = map chr(0) x int( ( @words + 8 )/8 ), 1 .. 26;

for my $iWords ( 0 .. $#words ) {

    for my $char ( sort uniq split '', $words[ $iWords ] ) {
        vec( $index{ $char }, $iWords, 1 ) = 1;
    }
}

while( chomp( my $given = <STDIN> ) ) {
    my @given = split '', $given;
    my @excludes = grep{ !(1+index $given, $_ ) } 'a'..'z';

    my $mask = chr(0) x int( ( @words + 8 )/8 );

    $mask |= $_ for @index{ @given };
    $mask &= ~ $index{ $_ } for @excludes;

    vec( $mask, $_, 1 )
        and finalCheck( $words[ $_ ], $given )
        and print $words[ $_ ]
        for 0 .. $#words;

    print "\n\n";
}

__END__
fred
def
fed
red
ref



apetpxl
ale
alp
ape
apex
apple
applet
apt
ate
axe
axle
eat
eta
exalt
lap
lappet
late
latex
lax
lea
leap
leapt
lept
lepta
let
pal
pale
pap
pat
pate
pea
peal
peat
pelt
pep
pet
petal
plat
plate
plea
pleat
tale
tap
tape
tax
tea
teal
[download]

BTW: Your example helped, but is badly chosen. The problem was never including words that contained characters not in the supplied list (your 's'), but rather words that contained too many of one or more of the given letters. Eg. the second 'e' in 'freed' given 'fred'.