Is there a way that you can create some kind of hash of the message, representing the similarity-key (like soundex, for example), and then use that hash-value of the message as the key in an index-hash?

I'm not familiar with Text::Levenshtein, but if it can work by returning some kind of a hash or a "score" of the message, then you can do something like:

foreach my $message (...) {
   ...
   my $score_range = floor($score/$threshold);
   $index{$score_range} ||= [];
   push @{$index{$score_range}}, $message;
}
[download]

And then you can only do your comparison against those messages in whose the hash for $score_range-1, $score_range, and $score_range+1. I hope that psuedo-logic is followable... and if I messed up the boundary case a little, well, you can deal with that, but you get the idea.