Strange. I never saw such a phenomenon on my iPod video on 3.4, and I just tested it on 3.5:
Load my "all tracks shuffled" playlist.
Skip to the next track
Wait 10 seconds.
Skip back to the beginning of the song.
Wait 10 seconds...
... and it kept playing 11, 12, 13 seconds and so forth.