decode_json uses JSON::true or JSON::false for the first instance it comes across, but then adds hash references to an existing true or false for all subsequent instances.

No, not quite.

When JSON::XS is loaded, it creates two objects

$JSON::XS::true  = do { bless \(my $dummy = 1), "JSON::XS::Boolean" };
$JSON::XS::false = do { bless \(my $dummy = 0), "JSON::XS::Boolean" };
[download]

No other instances are ever created. No references to those are created. Those two objects are used everywhere.

There's probably a neat way to use Rmap to do the walking, but it was beyond my abilities I'm afraid. :(

It's refusing to visit the same reference twice. You could probably mess with its seen method (which appears to be a way at peeking at the module's internals).