Why doesn't my iPod Classic show all the songs it holds?
Could it be that some albums are tagged as "Compilation"? In this case the artists in these albums are not shown in the "Artists" submenu... Uncheck the "Compilation" check-box (or something like that - I don't use iTunes!) in the Information tab and they magically appear in the list.

PS. When you select an artist that "has" a proper album, the songs in the Compilation albums are also shown.