In reply to:

---

If this isn't an exaggeration, then this could potentially be a bug, depending on the mix of tunes existing on the player and the exact steps you used to create this situation in the first place.

What version of the firmware is the player running? How many tunes by how many different artists are on the player?

---

I usually listen to a playlist of about 1000 songs by about 40 artists, or a genre with about 150 tracks by 5 artists, and I definitely see at least to most recently played ordering, although not strictly so.

Real example: I was just listening to that genre, then did menu-play music-playlist-playlist1-play all tracks and I got:
4 tracks I re-ripped the other day and haven't listened to yet, three random tracks, 6 tracks by an artist I have two discs of, two random tracks, 7 more by the same artist of the previous run, then it looks somewhat random. After re-shuffling it still looks similar.

I have firmware 1.41.