The shuffle feature is random, if you have a selection of 1,2,3,4,5 then 1,1,1,1,1 is a possibility for a 5 song playlist. Random means it can take any of the songs and play them at any time. It's not like the lottery where if a number is drawn then it is no longer available for selection, in this case, all songs are available at all times for example:
Lottery method:
1st Selection
1,2,3,4,5 -> say it chooses number 3
2nd Selection
1,2,4,5 -> 5
3rd Selection
1,2,4 and so on.
iPod shuffle method:
1st Selection
1,2,3,4,5 -> 3
2nd Selection
1,2,3,4,5 -> 3
There is nothing to say the iPod or iTunes cannot select a prior song for the next played.