Maybe specify which iOS version you're using.
If you have iOS 5, try going into Settings/Music and change the "Group by Album Artist" setting, does that help you? Probably not, but if you haven't tried it give it a shot.
I say "probably not" since there seems to be something goofy with iOS 5 (on my iPhone at least, my Touch is a 2G stuck at iOS 4 and does not behave the same). On my iPhone I see the following behavior:
1- There is an Artist entry for "Various Artists", which is all my compilations, despite there being a separate Compilations menu selection. This is fine, just redundant.
2- Artists who only exist on a Compilation album do not appear in my Artist menu. This is good, and was a shortcoming in all previous iOS versions. Now my Artist menu is not cluttered up with one-hit wonders from Compilations. The odd thing though is that despite the "Group by Album Artist" setting, that does not impact this one way or another, I would think it should. Oh well, I like it how it is now.
3- HOWEVER, for Artists who exist on a Compilation album and a "regular" album, their Compilation songs do not show up under their respective Artist entry, only songs from the regular albums do. That is a problem since there is no way to play all songs by an artist if some of their songs are on a Compilation. My iPod Classic would bring Compilation songs into the Artist menu if the artist had at least one other album on my iPod, which is the preferred approach. My 2G Touch does it this way too, but only because it can't separate Compilations at all, other than the dedicated menu for them.
So, it could be that what the OP is seeing is this 3rd issue -- once you mark a song as "Part of a Compilation" they are always removed from the Artist menu, regardless if there are other songs by the artist that are not on a Compilation.