Maybe the problem arises when trying to cycle through all keys of the hash at the exact same time its contents are being updated:

That makes a certain amount of sense in the version above with the sleeps removed. It's quite easy to see how (without locking) that the hash iterator could be corrupted. But that does not explain the earlier versions where you have sleeps that effectively orchestrate serialisation of the writing and reading of the hash.

Yes, you should be using locking. But for locking to be the fix for the original (with sleeps) version of the code, it would mean that iterating a 2 key hash would have to take longer than not just one timeslice (in order for the other thread to have a need to lock), but longer than 1 second. And that's just silly.

A quick test shows that Perl can iterate a two-key shared hash 10 million times in just over 4 seconds:

use threads; 
use threads::shared;
use Time::HiRes qw[ time ];

my $h:shared = ( 1..4 ); 
print time; 
for ( 1..1e7 ) { 
    1 while each %h;
}
print time;

1227886927.80338
1227886932.10025
[download]

Even on a multicore box and with Data::Dumper in the mix, there's no way that the sleeping version of the code you posted could be concurrently modifying and iterating that hash.