I had the same problem - 3999 songs in iTunes, 3998 songs on my iPod. I eventually tracked it down to a compilation CD that had two versions of the same song, recorded at different times. When the CD was imported the files in the iTunes library on my HD were created as Big Party.mp3 and Big Party 1.mp3, even though both were listed in iTunes itself as Big Party. The iPod ignored Big Party 1.mp3 so I renamed it in iTunes to Big Party (version 2), synched the iPod and got both versions.
Try looking for duplicate song titles on the same album and see if that's your problem.
edit: BTW To find the missing song I sorted my iTunes library by song title and copy-and-pasted the entire song list into an AppleWorks spreadsheet, then did the same for the tracks on the iPod and pasted them in the next column on the spreadsheet and skimmed through until I got a mismatch in song titles - the missing song was just a couple of hundred songs from the bottom...