Hmmm... Pretty sure there are no ID3 tags, but I could be wrong. In any event, the same exact files run just fine on my iAudio X5 RockBox (ver. r19569-081223--same as on the iPod). Maybe I just need to reinstall RockBox on the iPod...
To answer the earlier question regarding the encoder, I don't recall, but it was probably the default Ogg Vorbis encoder, which I think is oggenc. Once I can find the CD I will try to re-rip, but since the files work everywhere but the iPod, the problem has to lie there.
======EDIT======
(What's with this "no double-post" shite?)
I just used id3info on these files and they did indeed have ID3 tags. I ran id3convert -s *ogg to strip them of their tags and re-copied to my iPod. The songs play now(!)
Thanks for your hint!
Now, if I can just figure out the seemingly-random problem of the database storing the song names multiple times...