iTunes has issues with some mp3s. Try:
MP3 Scan+Repair - an ID3 tag evaluator for the Mac - http://discussions.apple.com/thread.jspa?threadID=2020936
MP3 Scan+Repair (including sources): http://triq.net/mac/mp3-validator-mac-os-x
Edit:
On closer reading of your post I am wondering if you mean files you purchased from Apple. Those are not mp3s but aac/mp4. iTunes sometimes doesn't keep track of adding files. I've seen this reported several times here recently.
What happens if you restart iTunes?
Look in the Recently Added playlist. What happens if in the Get Info window you add the lettter (any letter actually) "X" to the end of the artist name, then remove it?
Right click on a problem file in the Recently Added playlist and then Show In Playlist > Music Do you see it?
Delete the files from iTunes but do not let iTunes move them to the trash. Now go to where they are located in Finder and add them again. Does that work?
If you don't see it in Recently Added, make a new playlist window and drag the files from where iTunes put them to an empty playlist. Do they show?
Message was edited by: Limnos