That's kinda strange, as (IIRC) weak refs were introduced with v5.6.0.
Also, FWIW, I can't replicate the problem with v5.8.4 (on Linux) with any
combination of Scalar::Util 1.13 / 1.19 and Test::Deep 0.096 / 0.100.
Other than that, there's a note in the current Test::Deep CHANGES file:
Don't explode on perl's that don't have weakrefs. If they're not
available, just don't weaken the refs. It means refs can be cached for
longer than desirable but it's better than explodiing.
This doesn't fix all of te problems with perl 5.005 but I'm pushing it
out because the previous version number upsets CPAN.pm.
IOW, the current version should work (even with perls that truly don't support weak refs...).