You could take your original idea of splitting the list across files keyed by first letter one step further and split them into subdirs named for the first letter and then files by the second. This would vastly reduce the memory overhead for the look up.

I did this with my own words file containing over 600,000 words and then wrote a small sub to read the appropriate file and a m// to check for its existance and in a thoroughly unscientific benchmark used it to look up a word in the largest subset of each of the 26 first letters and it came out approximately 20 ms/word which should be fast enough for almost any purpose.

The program to split the words file

my ($oldfirst, $oldsecond) = ( '', '' );

open WORDS, '<',  $ARGV[0] or die $ARGV[0] . $1 . $/;
while(<WORDS>) {
    chomp;
    next if length == 1;
    $_ = lc;
    my ($first, $second) = /^(.)(.).*/;
    $first = './' . $first;
    $second = $first . '/' . (($second eq ' ') ? '_' : $second);

    if ( ($first ne $oldfirst) or ($second ne $oldsecond) ) {
        mkdir $first if not -e $first;
        open SUB, '>>', $second or die $second . $! . $/;
    }
    print SUB $_, $/;
    ($oldfirst, $oldsecond) = ($first, $second);
    print "\r$second:$_              ";
}
[download]

And the program for doing the lookup.

#! perl -sw
use strict;
use Benchmark::Timer;

sub IsWord {
    return if not @_ or length == 1;
    my ($word, $first, $second) = $_[0] =~ /^((.)(.).*)$/;
    local $_ = do{ local (@ARGV,$/) = "./$first/$second"; <> };
    return /^$word$/im;
}

my $timer = Benchmark::Timer->new(skip=>0);

for (@ARGV) {
    $timer->start;
    my $IsWord = IsWord( $_ );
    $timer->stop;
    print $_, $IsWord ? ' is ' : ' is not ', 'a word', $/;
}

$timer->report;
print "@{[$timer->data('_default')]}", $/;

__END__
[download]