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.

The problem comes about I think when you are constantly opening the iPod app on your iPhone and starting again each time in shuffle mode rather than resume. So the playlist gets regenerated each time. I feel like there are songs I've heard 50 times and plenty of songs I've never heard come up. Would be much better if it aimed for an even distribution.

My algorithm for playing songs indefinitely in a random order:

1. let S = set of songs to be played

2. let N = number of songs

3. repeat until bored:

3.1. let R = set of last [N / 2] songs we played

3.2. pick a song at random from S \ R; play it

You may want to tweak step 3.2 to give higher probabilities of picking songs that haven't been played for longer.

You mean: Shuffle should shuffle, like a deck of cards, and not draw with replacement?