This is more a computer problem than a specific ipod problem. It could be that certain songs written to the ipods hdd are now fragmented or suffering from bad sectors. The skipping would occur because the system is coming up with a bad enough data stream it can't decode it anymore thus you get short pauses as the drive actuator flails around looking for something to read. (Kind of like the anti-skip in some portable cd players not working if you shake the player long enough)
The solution is to either delete those songs and try writing new ones on to it, or to reformat the ipod complete as
this site promotes it. Or maybe you could try
defragging it. YMMV, and since I don't have one of those overpriced lumps of ceramic and plastic, take any advice I give with a large grain of salt.