In 2004, Gracenote lost a suit against Musicmatch. This opened the field to more competition. Microsoft Windows Media Player moved to the service provided by All Media Guide. Lots of action at present.

I seldom recommend Wikipedia for information because of their lack of peer review and inaccuracies, but their writeup on Gracenote, now a little out-of-date, contains useful links to the Court action and to other players in the game.
http://en.wikipedia.org/wiki/Gracenote.

Richard Bridge's reference to 'international law' is amusing, perhaps he would explain what that is. Most of the big players in services operate internationally one way or another and have rights in many jurisdictions. Gracenote is a partner in Japanese technology companies which have helped them to operate globally.

The situation at present is very complex.