Heuristic solutions can be improved. For instance, the following modification to your refinement algorithm shows an even better solution:

## Explore all improvement paths from the current best guess
## Since multiple paths are explored simultaneously - only print overa
+ll improvements
## Limit execution time to specified timeframe

my %seen;
eval {
    local $SIG{ALRM} = sub { die "Timed Out\n"; };
    alarm 60;
    my @work = [$best, \@guess];
    while (@work) {
        my $item = pop @work;
        my ($cur_best, $cur_guess) = @$item;
        for my $idx (0 .. $#cats) {
            for my $word (@{$cats[$idx]}) {
                my @new_guess = @$cur_guess;
                $new_guess[$idx] = $word;
                next if $seen{"@new_guess"}++;
                my $new_tot = calcScore(\@new_guess);
                if ($new_tot > $cur_best) {
                    push @work, [$new_tot, \@new_guess];
                    if ($new_tot > $best) {
                        $best = $new_tot;
                        print "$best : [ @new_guess ]\n";
                    }
                }
            }
        }
    }
    alarm 0;
};
[download]

It finds the following in under a second and finishes off the work queue in about 17.

446 : [ odysseys sleekest steepen spindles baseless marshals pastels s
+talest shambles exhausts ]
[download]

I am still looking for a trick given a specific dictionary (60K words) to be able to produce a guaranteed optimal solution in a reasonable run time (see How many words does it take? for an example of such a trick). In the interim I have been exploring a number of heuristic solutions and refinement algorithms.

Your heuristic approach with my refinement is always able to tie or beat the "best" solutions of the other heuristic approaches. Unfortunately, in the cases when there is a tie, the other approaches reach the optimal solution faster. I am trying to figure out if there is a way to prune the work queue above so that it produces the same results faster.

If you are interested in the approaches I am exploring (either for heuristic or guaranteed optimal) let me know. I am seldom interesting in activities with "useful purposes" so don't feel obliged to indulge me if you aren't interested :-)