You have received really good answers already (points all round) so if you don't mind I'll just don my consulting hat for a moment and provide a different viewpoint.

You have a scalar variable $FIXED_STRING to which you assign a literal string once and never change it. Bonus points to you for choosing an appropriate name for your scalar! However, if this is a real indicator of your situation why not side-step the problem entirely by using a constant instead? In that case your block becomes:

{
    use constant FIXED_STRING => 'fixed_string';
    my %persistent;

    sub do_something {
        my $x = $_[0];

        $persistent{$x}{FIXED_STRING} = rand;

        END {
            for my $k (keys %persistent) {
                print "$k: $persistent{$k}{FIXED_STRING}\n";
            }
        }
    }
}
[download]

and you do not need to worry about compile-time vs run-time or returning subs or any of that. This might be considered a work-around and that's just fine - sometimes a work-around is precisely what is required.

Update: Haarg has spotted the flaw here and supplied a fix in his reply (++).