[pkscout]

When I first started up XBMC, I played music randomly from a playlist. Nine Inch Nails came up and did not download any artwork (using Fanart.tv)
Alex Clare came up and displayed previously downloaded artwork
Type O Negative did not work either, then I stopped the music and shut down XBMC

I see what's happening. AS isn't technically broken, but the challenge with getting a valid Musicbrainz ID is showing in your case. Let me see if I can explain. And if you make it to the end, I actually have a couple of suggestions.

Fanart.tv (and theaudiodb.com) require a MusicBrainzID to lookup stuff for a given artist. To try and get that, AS queries the MusicBrainz database to try and get a match based on the information from the song that's playing. Because MusicBrainz tries to give you a long list from which to choose, AS has to ask lots of different questions to try and get down to one answer. Here's the logic:

1- ask for a list of artists based on the artist name of the playing song
2- go through that list looking for a complete match (i.e. Nine Inch Nails is the actual group name, not Nine Inch Elvis - which is also returned as a result when searching for Nine Inch Nails).
3- If you find one, ask for all the albums for that artist.
4- go through all the albums and look for a match. This is a little bit of a fuzzy match, and I think I could add some additional fuzziness that might actually help in your case.
5- if no album match, get a list of every song by an artist and see if you can find a match. Again, the matching is a little fuzzy.
6- At this point you either have a match or you don't. If you do, AS stores the MusicBrainz ID. If not it writes out an empty file. If it finds a match, AS will never check again for that artist. If there was no match, it will try again in a couple of weeks.

In your case, the two artists with no artwork don't have any because when AS tried to get a MusicBrainz ID, it couldn't. In the particular log you sent, AS already failed to find a match, and it probably hasn't been two weeks yet. It's possible in a couple of weeks you'll be playing stuff and the artwork will download.

One thing you can do is go look up the artist on MusicBrainz to see how the albums and songs are named. Then you can decide if you want to rename some of your music to match. If you decide to do that, go to the XBMC data directory (location will vary based on platform) and look in userdata/addon_data/script.artistslideshow. You can either delete the entire ArtistInformation directory or just the one for the particular artist. That will force AS to try and find the MusicBrainz ID again. Alternatively, you can open the empty musicbrainz.nfo file and past the correct MusicBrainz ID into that. Then AS will use it to get the artwork.

I know this is a bit complicated and a pain in the ass. At some point I'm hoping XBMC adds the ability to scrape the MusicBrainz ID when you scan your music library. Once that happens, AS is already ready for that. In Frodo the field is in the database, and I even ask XBMC for the MusicBrainz ID, but the information is rarely if ever there. My understanding is that Gotham will scrape the MusicBrainz ID if it's in the metadata of the music file. I think I saw a MusicBrainz scraper once, but I really don't have any idea what it scrapes.

I'm hoping somewhere in this ramble was something that will help you out.