My suggestion is to do a Restore, not just Reset (restart) the iPod. If you did a Restore already, the cause is probably those song files being corrupted, since they also had this problem on a different older iPod (which was not clear to me when I read your post).
Song files (like all computer data) can become corrupted on the computer. The problem may not be severe enough to affect playback on your computer using iTunes. But an iPod is a simple media player and not as tolerant, compared to a powerful computer. You should replace the song files from a backup (before the corruption occurred) or the original source. If they are songs purchased from iTunes Store, you can remove those songs from your iTunes library and download them again at no cost
Download your past purchases - Apple Support
If they were imported from music CD, import them again. Otherwise, replace from original source. (Try it with one of these songs, to see if problem gets resolved.)
You may want to do a general check of your computer's drive, in case data corruption is not confined to just some song files (because the drive is becoming unreliable). If it's a Mac, run Disk Utility and use First Aid. When you do this, select the drive volume in Disk Utility's sidebar, not the drive device. The drive volume is indented below the device in sidebar. If your computer is a Windows PC, do the equivalent check in Windows.
