Basically the problem is that Safe creates a new environment and the class into which your data has been blessed is not the same class that exists in our normal environment.
use Safe;
use Devel::Peek;
my $r = 'bless \\ do { my $x = 0 }, "x"';
print Dump(eval $r);
print Dump(Safe->new->reval($r));
print Dump(eval $r);
print Dump(Safe->new->reval($r));
Which outputs (on my machine at least):
SV = RV(0x1847158) at 0x1830630
REFCNT = 1
FLAGS = (TEMP,ROK)
RV = 0x182fa48
SV = PVMG(0x18a9974) at 0x182fa48
REFCNT = 1
FLAGS = (PADBUSY,PADMY,OBJECT,IOK,pIOK)
IV = 0
NV = 0
PV = 0
STASH = 0x18d8620 "x"
SV = RV(0x1847188) at 0x18d8b24
REFCNT = 1
FLAGS = (TEMP,ROK)
RV = 0x18d8b00
SV = PVMG(0x18a8f34) at 0x18d8b00
REFCNT = 1
FLAGS = (PADBUSY,PADMY,OBJECT,IOK,pIOK)
IV = 0
NV = 0
PV = 0
STASH = 0x18d8b54 "x"
SV = RV(0x1847180) at 0x18d88fc
REFCNT = 1
FLAGS = (TEMP,ROK)
RV = 0x18d8920
SV = PVMG(0x18a90f4) at 0x18d8920
REFCNT = 1
FLAGS = (PADBUSY,PADMY,OBJECT,IOK,pIOK)
IV = 0
NV = 0
PV = 0
STASH = 0x18d8620 "x"
SV = RV(0x1847188) at 0x18d8b18
REFCNT = 1
FLAGS = (TEMP,ROK)
RV = 0x18d8a28
SV = PVMG(0x18a90f4) at 0x18d8a28
REFCNT = 1
FLAGS = (PADBUSY,PADMY,OBJECT,IOK,pIOK)
IV = 0
NV = 0
PV = 0
STASH = 0x18d8b90 "x"
Notice how the stash has the same address for both the first and third runs. The second and fourth entries (those that are both from new Safe environments) have stashes where the address does not match either. This is because the x namespace in our environment is not the same as the one in either of the Safe compartments we created. I'm curious which version of CGI::Session you are using since I submitted a crummy fix that walks the structure and reblesses everything in place in the 4.x version (__walk in CGI::Session::Serialize::default).