Thank you all for the responses, just to address a few points brought up..

First and formost, the code above is not representative of the data structure I was using other than in a vague, hash of hashrefs type of way. I do use numbers, but theyre not sorted etc, still need to be in a hash :)

Secondly, with regards to "exists", the problem became apparent because I was attempting to use exists as part of the flow of the code.. briefly:

$asked = exists($href->{$qid});

if ($asked) { #do stuff }
else { #do other stuff }

# later

%data_structure = (
  key => value,
  key2 => value2,
  key3 => $href->{$qid}{answer} || 'stuff',
  #more assignments
);

#do things with the data structure
[download]

The first loop through the code would work fine, further loops would later would raise warnings (when doing data validation). Once I saw/replicated the problem, it was the lack of warnings on the first loop that raised my eyebrows.

I hadn't heard of locked hashes, time to do some reading (though they don't look applicable for this particular issue at first glance)