[pkscout]

Please find debug log here (AS brought back only last.fm truncated bios for the three artists)

A little preamble to explain how AS tries to find a MBID for an artist so that my explanation of your issues will make some sense. The MusicBrainz server prefers to give you back lots of possible matches for a given search, but AS would really like "exact" matches. Because of this, AS uses the following procedure to search MusicBrainz:

1- ask MusicBrainz for a list of artists that "match" the currently playing artist
2- take that list and iterate through it looking for an artist whose name exactly matches the currently playing artist
3- when an exact match is found, ask for a list of all that artist's albums
4- iterate through the album list looking for a "begins with" match for the currently playing album (i.e. "Legend" would match "Legend of a Band")
5- if AS finds a match, it returns the MBID for the artist
6- otherwise ask for a list of all the songs for the artist
7- iterate through the song list same as above but matching on currently playing song
8- if AS finds a match, it returns the MBID
9- if no match, go to the next matching artist and start the whole thing again
10- if nothing is found, return an empty string

So now to your three songs:

1- AS finds an artist matching Marillion, but no album or song match. Why? Because the name of the album in MusicBrainz uses the extended character for an apostrophe, but you are using the single quote. A small difference, but it is the difference between match and no match.
2- AS finds an artist match for Bob Marley & The Wailers, but no album or song match. Why? the MusicBrainz album name is "Legend:" instead of what you have, which is "Legend - " I didn't check the song, but the same logic applies.
3- AS finds no artist match because there is no artist named Tori Amos feat. Damien Rice. Multiple artists in XBMC must be separated by a " / " to be parsed as separate artists. AS also supports putting featured artists in the title of the song - i.e. song name (feat. artist)

This is the pain that is MusicBrainz support. So you have three options right now.

1- Fix your metadata so that it matches what's in MusicBrainz.
2- Override the artist bio (and potentially images and other info) with info from a local override file (see the wiki on how to do that).
3- Manually add the correct MBID to the empty musicbrainzid.nfo file in the Artist Information directory.

All of these will be time consuming, and the third one would be a downright pain in the ass.

Having said all that, if you really are storing the MBID as a tag in the MP3 file, then there might actually be an XBMC built in way to get that back. Could you somehow get me one of your MP3 files so that I can see how the tags are constructed? No guarantees, but I'll look at it.