Yes, I agree. I would like the same functionality that you describe.
Strangely I found this a while back as well and it bothered me, but I just turned on 'Shuffle'.
However, I just went down to the car to check this out (ok, I *do* believe you!) ,and my unit is now shuffling properly. I.e. with the behaviour that you describe:
Root Level (i.e. down x 3) - Plays random songs in the unit (actually from every play list - so I get 'The Corrs' all of the time

).
Level One - Plays random songs from the playlist.
Level Two - Plays Random songs from the artist
Level Three - Plays Songs in Order from the CD.
Playlist as follows:
Root.
......Playlists
......'By Artist'
..................Sheep on Drugs
.................................Greatest Hits
etc.etc.etc.
In short, I've no idea how, but I've managed to get my unit to replicate exactly the behavious that I want and you describe.
?!?
Paul.
Paul Haigh, 6GB, Blue
Reg: 4120 - Serial 00254