Sorry, I missed that the first time (as did some others). Here is a quick fix. Replace the final loop with this:

while ((my $key, my $value) = each %hash) {
    print "the Key is: $key\n";
    my %seen = ();
    # Perl Cookbook 4.6  Extracting Unique Elements from a List
    my @uniq = grep { ! $seen{$_}++ } @$value;
    print join("\n",@uniq),"\n\n";
}
[download]

Update: I see that Ovid also has a good one-pass solution.