Does it really? I can't really test this because I don't have an iPod shuffle, but in iTunes shuffle+repeat will

  1. generate a random permutation of the playlist
  2. play all the way through it
  3. goto 1

This does mean that for a playlist of N songs, you'll hear the same song consecutively about once every N^2 songs.