And here is my solution that walks a trie and the boggle board in parallel. You need to have a dictionary file which is a just list of words, one per line. Then you run the code like:

# To get a random 4x4 board and solve it:
boggle < dictionary
# To get a random board of a different size:
boggle 5 < dictionary
# To use a specific board:
boggle gaut prmr dola esic < dictionary
[download]

An example run on the above sample board finds 229 words plus 20 repeats using the 172823 words in my copy of the enable1 word list.

#!/usr/bin/perl -w
use strict;

$|= 1;

my $width= 4;
my @board;
if(  1 == @ARGV  ) {
    $width= shift @ARGV;
}
if(  @ARGV  ) {
    $width= @ARGV;
    die "Invalid board (@ARGV).\n"
        if  @ARGV != grep /^[a-z]{$width}$/, @ARGV;
    @board= (
        '!', ('!') x $width,
        map( {; '!', /./g } @ARGV ),
        '!', ('!') x $width, '!',
    );
}

my %trie;
my %freq;
my $nWords= 0;
my $nLets= 0;
while( <STDIN> ) {
    chomp;
    $nWords++;
    my $pos= \%trie;
    for my $let ( /./g ) {
        $freq{$let}++;
        $nLets++;
        $pos= $pos->{$let} ||= {};
    }
    undef $pos->{'.'};
}
print "$nWords words added to %trie.\n";

if(  ! @board  ) {
    @board= (
        '!', ('!') x $width,
        map( {; '!', map( randLet(), 1..$width ) } 1..$width ),
        '!', ('!') x $width, '!',
    );
}
my @dir= (  -$width-2, -$width-1, -$width, -1,
            +1, +$width, +$width+1, +$width+2 );
for( 1..$width ) {
    print join ' ', '', @board[ $_*($width+1)+1 .. ($_+1)*($width+1)-1
+ ], $/;
}

my %found;
my $repeats= 0;
for my $start (  grep '!' ne $board[$_], 0..$#board  ) {
    my @used;
    my @pos= $start;
    my @idx;
    my $word= '';
    my @tree= \%trie;
    while( @pos ) {
        my $let= $board[$pos[-1]];
        my $tree= $tree[-1]{$let};
        if(  ! $tree  ) {
            pop @pos;
        } else {
            $used[$pos[-1]]= 1;
            push @tree, $tree;
            push @idx, 0+@dir;
            $word .= $let;
            if(  exists $tree[-1]{'.'}  ) {
                if(  ! $found{$word}++  ) {
                    print 0+keys(%found), " $word\n";
                } else {
                    $repeats++;
                }
            }
        }
        while(  @pos  ) {
            if(  ! $idx[-1]  ) {
                chop $word;
                $used[$pos[-1]]= 0;
                pop @pos;
                pop @idx;
                pop @tree;
            } else {
                my $pos= $pos[-1] + $dir[--$idx[-1]];
                if(  ! $used[$pos]  ) {
                    push @pos, $pos;
                    last;
                }
            }
        }
    }
}
print "plus $repeats repeats\n";

sub randLet
{
    my $cnt= int rand $nLets;
    for( keys %freq ) {
        $cnt -= $freq{$_};
        return $_   if  $cnt < 0;
    }
    die "Impossible";
}
[download]

Update: Removed off-by-one error in counts displayed for found words.