Along that line of reasoning - you could also try an oldest or most-played shuffle of the complete playlist. This should eliminate the playlist size as being the cause.