If you search for an artist and you don't find it, you are shown an "Add artist" link (which pre-fills part of the form with your query); however, if you do the same for a label, you are not shown any "Add label" link.

Compare e.g. http://musicbrainz.org/search?query=prova123&type=artist and http://musicbrainz.org/search?query=prova123&type=label.