nobody promised you that keys and values would return in the same order

Yes, they did. Read the quoted docs more carefully:

The values are returned in an apparently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be the same order as either the keys or each function would produce on the same (unmodified) hash.