Welcome to the Rockbox Technical Forums!
Have you actually, while NOT restarting the playlist (resuming playback) kept track of every song that plays and tested these findings? The playback is actually not "Random", it's just shuffling a list. You can look at the list and verify every single song in it, and their new, shuffled, positions.
The shuffle algorithm we use is called the Fisher-Yates algorithm, and is generally accepted as a good shuffling algorithm.
Seems like this page could use an update by someone well-brained on the subject: http://www.rockbox.org/twiki/bin/view/Main/ShuffleExplained
Have you done some actual testing, or are you just going off "I notice the same artist several times"?
Page created in 0.345 seconds with 20 queries.