Consider the following code:

#!/usr/bin/env perl

use strict;
use warnings;

print "1. Before calling foo\n";
foo();
print "2. After calling foo\n";
{
    print "3. Beginning of block\n";
    sub foo {print "4. Inside foo()\n";}
    print "5. End of block\n";
}
print "6. After block\n";
[download]

The order printed will be 1, 4, 2, 3, 5, 6. In your code, your definition of $FIXED_STRING happens in position 3, which happens after the sub call (position 4). The 'my' declaration happens at compiletime. The definition happens at runtime, and run time happens line by line unless flow is altered by a loop, subroutine, conditional, exception, or other control of flow mechanisms.

Really the best solution is to manufacture your closure through a subroutine:

my $foo_stuff = make_foo();

$foo_stuff->{'foo'}->('bar');
$foo_stuff->{'foo'}->('baz');

$foo_stuff->{'dump_foo'};

sub make_foo {
    my $FIXED_STRING = 'fixed_string';
    my %persistent;
    return {
        foo => sub {
            my $x = $_[0];
            $persistent{$x}{$FIXED_STRING} = rand();
        },
        dump_foo => sub {
            for my $k (keys %persistent) {
                print "$k: $persistent{$k}{$FIXED_STRING}\n";
            }
        }
    };
}
[download]

This strategy would certainly work reliably (assuming I didn't submit a typo).

I'm not thrilled with needing to return accessor subs for both setting and dumping. It feels like we're going in the direction that is satisfied by object systems. But it pains me to say that because, I love the elegance of subs manufacturing subs capturing closures.