This really is MESS, and I made a mess of my Library trying to fix it! I bought some .mp3 files from Amazon.uk (all 10p cheaper than iTunes Store) and experienced the same problems as everyone else in this thread - the songs appeared in Recently Added and then when I played them, in Recently Played, but not in the Library. I waited 24 hours, but they still didn't show up in Library. Finally I managed to make them to appear by highlighting all the files in Recently Played and (from right click) created AAC files. I immediately got the whole lot, .mp3 and .m4A (AAC) and some duplicates too, all showing up in my Library!
I have iTunes 11.0.1.12 and my PC runs under Windows. I used Windows Explorer to find the songs in my iTunes Music folder and deleted all but the .m4A files. However, all the other versions were still showing in my Library, mostly in triplicate, with no indication of which were real. To clean up that mess, I had to try and play all the songs to identify which were the .m4As and use Shift/Delete to delete all the ones that came up as not found. Thank the deity that it was only a few files - it still took me hours to figure all this out.
Too much to hope that Apple would help with or even acknowledge this monster fail in the latest iTunes version! The conspiracist in me thinks it's deliberate. Good luck.