It seems I'm not the only one unconvinced by Rhythmbox's shuffle mode. No sooner I mention it on the local IRC than one of my colleges points at some work he did over Christmas. While I've not got time to start running around patching my work box with a suitable new version I am now using the "hidden feature" of clicking Shuffle and Repeat which turns on the true random mode rather than the list based mode which is somehow flawed. According to Dave he's looked at the shuffle code which looks right and should ensure every song is played only once before it is regenerated. However the last few days I've been having repeating songs within 4 or so hours and my library is somewhere in the region of 8000 songs. It's been posited the list is either wrong or being regenerated too often. I'll add it to the list of things to look at should I ever have time.