That was my initial thought on looking at this, but it doesn't bear out. It's the values you want in random order; random keys are selected for each value. The fact that values() doesn't return a truly random order based on the keys doesn't matter.

Update:
You could bypass all issues of ordering based on hash storage by replacing the values %foo with @foo{sort keys %foo}. Then (assuming a hypothetical keysof() function that returns the key for a value), values would be returned in order of sorted keysof(x), while plain values(%foo) (assuming a hypothetical order() function that returns the index into the keys %foo list of a particular key) is in order of sorted order(keysof(x)). Since keysof(x) is a random number between [0 and 1), order(keysof(x)) is equally random for each x, notwithstanding order()'s lack of randomness wrt its argument.