I have found the current
Replay Music tagging - even with the latest software, to be lacking. The free database is, well, free . . . and Amazon, etc., don't have everything.
So this is what I do and it works 95 percent of the time - especially when recording from places such as Pandora and Last.fm, although Last.fm works better if you use thelastripper, but that's another story.
Anyway, what I do is open WinAmp, the free version; cut and paste all the song titles that aren't identified into the "playlist" window (upper right hand corner); highlight all the songs, then right click on your mouse and choose "send to" and then choose "auto-tag" from the next popup windows. WinAmp, I believe, still has access to the Gracenote DB, and if it's not that one it's better than what Replay Music uses. (I have been a Replay Music user for a decade; if they don't like the criticism and suggestions, they can fix their product).
This will, as I said, work about 95 percent of the time. It takes a little longer, but you get far more songs identified.
gm