If random songs start skipping, the cause is likely to be on the iPod. If it's always the same songs that skip on the iPod, even after a Restore and re-load, then the cause is likely to related to those particular song files, in some way, as currently stored on your computer. It does not necessarily mean "corruption." There could be something usual about the way those particular songs are encoded, that iTunes on the computer can handle, but the less flexible iPod cannot tolerate.
As a test, if you have songs with this problem that came from a music CD (and you easily find that CD), try removing that album (or just the songs with this problem) from your iTunes library, and re-import them from CD using iTunes (as either standard MP3 or AAC). If those songs are currently on your iPod, remove them so that they do not appear on the iPod. Then sync them to iPod again, with the "fresh" song files. Do the songs play properly on the iPod?