The first thing to check is to see if iTunes has marked those specific songs to end early. Next, try re-encoding the song at a lower or different bitrate and syncing it to the device. Often a glitch in the file can cause iPods to skip to the next song, but the same binary file plays through on macs with better code for handling errors. Lastly, it could be error creeping into the filesystem structure on the iPod. Once you're sure you've backed up everything from the iPod, you can enter disk mode and use Disk Utility (on the mac - on Windows there are lots of disk formatting tools) to zero the drive. That will test the actual hard drive for errors and spare out any bad blocks.
Feel free to edit this or comment if you find none of these helps narrow down the cause.
I have an alternative take on this problem:
I have just bought a Classic 160 Gb at Amazon few weeks ago and I have been facing the same issues as you.
I do not use Mac OS X, nor iTunes to sync. I run Linux and I use Media Monkey on a Windows VirtualBox Machine.
During the past two weeks I have tried everything that I could find. iTunes have not even been able to read my entire collection (strange, right?)
My findings
I have just restored the iPod firmware a few minutes ago. Started MediaMonkey and sync'd 10 songs from an ordinary random artist. Disconnected and the songs were there, nice. So the iPod is actually working. So far, so good, I have figured that out before.
However, in the meantime, while I was checking my library, I recalled that I have some songs from Japanese bands with Japanese characters in their names. Historically, this would be very error prone. So I did gave it a try, and sync'd 64 songs from that band. Disconnected the iPod and the songs were all gone.
So apparently the 2.0.4 firmware does not handle these characters very well. Check your library, make smaller tests. I am about to restore the iPod again and will try to sync some more files with normal ASCII characters. Will update you.
My old, now dead (waiting for a new disk), iPod, running 1.0.2 was able to hold those files nicely.
Best Answer
You can follow the troubleshooting options here, and if it still does not work, please let us know.
It's also sounding like there's a possibility of a failed HDD in that iPod. Using diagnostic mode, can you give us the details on the "Memory" SMART test?