I have like 4 songs under Bright Eyes in my 2gb Ipod Nano (Shut up. It was $30). But I put like 10 on there. All from the same album.
I just shrugged it off and I was on shuffle today and it played a Bright Eyes song that I don't have under the artist, but it's not anywhere else unless it comes up in shuffle.