You'll have to do that in three steps. First step:

my %hash = (
    'key1' => [1, 20, 3],
    'key2' => [1, 30, 4, 7],
    'key3' => [1, 9, 8],
    'key4' => [1, 9, 17],
    'key5' => [1, 9, 17],
);

my %rev_hash;

while(my ($k, $v) = each %hash) {
    push @{$rev_hash{$_}}, $k for @$v;
}
[download]

Now we have this:

%rev_hash = (
	'7'  => ['key2'],
	'8'  => ['key3'],
	'30' => ['key2'],
	'9'  => [ 'key3', 'key4', 'key5' ],
	'1'  => [ 'key1', 'key2', 'key3', 'key4', 'key5' ],
	'17' => [ 'key4', 'key5' ],
	'3'  => ['key1'],
	'4'  => ['key2'],
	'20' => ['key1']
);

Now let's lump together unique lists of values. I tried a more general approach trying to compare arrays as arrays at first, but it makes things much harder due to double bookkeeping. Since you just want the values concatenated to a string, the approach can be simplified drastically by doing that beforehand.

$_ = join ' ', sort @$_  for values %rev_hash;

my %inv_hash;
while(my ($k, $v) = each %rev_hash) {
    push @{$inv_hash{$v}}, $k;
}
[download]

Almost all the way there:

%inv_hash = (
	'key1'                     => [ '3', '20' ],
	'key3 key4 key5'           => ['9'],
	'key2'                     => [ '7', '30', '4' ],
	'key3'                     => ['8'],
	'key4 key5'                => ['17'],
	'key1 key2 key3 key4 key5' => ['1'],
);

We need to concatenate and reverse one final time:

$_ = join ' ', sort {$a<=>$b} @$_  for values %inv_hash;

my %revinv_hash = reverse %inv_hash;
[download]

And now we have:

%revinv_hash = (
	'3 20'   => 'key1',
	'8'      => 'key3',
	'9'      => 'key3 key4 key5',
	'1'      => 'key1 key2 key3 key4 key5',
	'17'     => 'key4 key5',
	'4 7 30' => 'key2'
);

There you go.

Makeshifts last the longest.