My original assumption was that keys would have to be called in a list context if I was to extract anything useful from it, and that calling it in scalar context would still cause a full traversal in order to count the key/value pairs.

As usual, it turns out Perl is a bit more clever than expected, so using keys to reset and each to pick a pair may indeed be the Right Thingtm even for a huge hash. Maybe perldoc -f each should point this out more clearly?