Short answer:
Plex is just bad at random items.
For whatever reason there's just some things it will refuse to identify correctly and it needs done manually.
There are settings where you can change what source it uses to identify. I don't use it for music, so I'm not sure if last.fm is an option, but as far as I know there's no way to set it up to check one place first than another if no result, you have to manually cycle.
So it really is just easiest to manually add the info the rare times you run into it.