I don't know if like the other iPods the shuffle has various shuffle settings. If it's primary shuffle directive is to shuffle albums, and you have only a few loaded, it might cycle through the albums without recognizing that a song has played already. If you have it set to shuffle by songs, then it shouldn't happen. I'm not sure if this is an option on the shuffle though.