It'll run in O(n^2), which is reasonable for what you're doing. However, you can speed that up some, so it runs in more like n log n, for the non-pathological cases.

foreach my $itemIndex (1 .. $items->Count)
{
    my ($body) = $items->Item($itemIndex)->Body =~ /MessageBody>(.*)<\
+/Mess/s;

    if ($body !~ /\S/)
    {
        die "Some appropriate error on index $itemIndex.";
    }

    CACHE_CHECK:
    foreach my $cachedItem (@cache)
    {
        my $compare = $cachedItem->[0];
        my $len = length($body) > $length($compare) ? length($body) : 
+length($compare);

        if (distance($body, $compare) / $len < $threshold)
        {
            @toBeMoved[$itemIndex, $cachedItem->[1]] = (1, 1);
            last CACHE_CHECK;
        }
    }
}
[download]

The primary differences here are:

1. I have made @toBeMoved into kind of a bit-flag. You loop through that list later and only deal with the items marked true
2. Once I find a match, I stop looking.

The second item is the major speed-up. You might not agree with it. If not, then get rid of the last. My thought was that your operation is transitive, or if A & B work and B & C work, then A & C will work. If that's not the case, then change it.