Actually, my guess is that this is a Compilation issue. If an album (or just a song) is tagged as "Part of a Compilation" it will not be found under the Artist menu if you have the "Compilation filter" activated on the iPod.
The first thing to confirm is if the items in question really are Compilations (e.g. an album consisting of multiple artists, not a "Best Of" album of a single artist that erroneously gets tagged as a Compilation by Gracenote's database errors).
If the items are not Compilations, go into Get Info and de-select that option. This is on the Options tab if you're editing a single item, or if you're going into Get Info for multiple selected items there is only one window and you'll find the Compilation check box there.
If the items really are Compilations, then you have two options:
(a) Turn the iPod's Compilation filter OFF. On the Classic I think it is Settings/Menu/Compilations/Off and Settings/Music/Compilations/Off. Turning off these Compilation menu items effectively lets all artists into the Artist menu, even if you only have one song by them from a Compilation album.
(b) Leave the Compilation filter ON, and access the item through the Music/Compilation menu.
Good luck!