Python dictionary: are keys() and values() always the same order?

Yes it is guaranteed in python 2.x:

If keys, values and items views are iterated over with no intervening modifications to the dictionary, the order of items will directly correspond.

Found this:

If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond.

On 2.x documentation and 3.x documentation.

Yes, what you observed is indeed a guaranteed property -- keys(), values() and items() return lists in congruent order if the dict is not altered. iterkeys() &c also iterate in the same order as the corresponding lists.