Although I'm not really sure why, the following code change seems to work:

#!/usr/bin/perl

use strict;
use warnings;

use utf8;
use Encode;

use Data::Dumper;
#$Data::Dumper::Useqq = 1;

binmode STDOUT, 'utf8';

our $VAR1;
my $data = 'ä'; # this is a non-ACII a Umlaut

my $dump = Dumper( encode( 'utf8', $data ) );

print $dump, "\n";
eval $dump;
print $dump, "\n";

if ( $data eq $VAR1 ) {
    print " == equal\n";
}
else {
    print " != not equal\n";
}
#print Dumper( $VAR1 ), "\n";

print "Data: $data\nVAR1: $VAR1\n";

print "original is utf8 = '" . utf8::is_utf8( $data ) . "'\n";
print "restored is utf8 = '" . utf8::is_utf8( $VAR1 ) . "'\n";
[download]

It's Dumper that generates the problems, not the eval:

$VAR1 = "\x{e4}";

has no way to determine that there's something utf8-related in the string.

Update: There's some additional info available here.

Update2: Looks like the proper solution is actually to just set

$Data::Dumper::Useperl = 1;
[download]

According to the doc, you just have to use a Perl newer than 5.8.0 to have this working - it does work for me, Perl 5.10.0.