Here's my crack at building your regexes.

sub genRegex{
    my $word = shift;

    my $re = '(.)';
    my @c =  split '', $word ;
    for my $c ( 1 .. $#c ) {
        my $match = 1+index $word, $c[$i], 0;
        $re .= $match <= $c[$i] 
             ? '($' . ($match - 1) . ')'
             : '([^$' . join( '$', 1..$i ) . '])';
        }
    }
    return qr[$re];
}
...

# Build a hash relating cryptoword with a regex to find possible match
+es.
$soln{$_}{regex} = genRegex $_ for @crypts;

open WORDS, '<words.txt' or die $!;

# build an HoA of all the possible matches
while( chomp( my $word = <WORDS> ) ) {
    print $word;
    for( keys %soln ) {
        push @{ $soln{ $_ }{ possibles } }, $word
            if $word =~ $soln{$_}{regex};
    }
}
[download]

Of course, once you have all the possible matches for each of the words in the cryptoquote, then comes the fun of trying to weed out the set(s) of words that use the same mapping function. That's left as an excersise for the reader...mostly because my first attempt would require a Cray to solve it in my lifetime:)