Musicbrainz? http://musicbrainz.org/doc/Development/XML_Web_Service/Version_2

GUIDs and XML make it slightly less nice, but otherwise it fulfills the criteria.