The problem is that most tags are badly written, and most software that displays songs only displays bare minimum. Typically tags I miss seeing: Style / Moods / Genres / Composers / Performers. Even Album Artist or Compilation tags are bad. Same with some misspelled tags, or inconsistent (is it 'D&B' or 'DnB' or 'Drum-n-Base', etc).
For the sake of argument, let's be platonic idealists for a second and say that a song is a concept and the files are simply recordings of performances—they're not "songs" at all, per se. Say I play "Black Betty" by Lead Belly. I get curious about the song, so I want to hear other versions of it. There's no way to express this data in ID3 or through a naming convention—it's just a reference to a concept that has no existence in a pile of MP3s—and it's hard to imagine a linking regime that would be maintainable. To do this, you need a place to put metadata that isn't attached to the files themselves, which can point to them. Note that this kind of scenario is not outside the OP's scope: they say in the article they are interested in providing all music to everyone, so these kinds of relationships would need to be documented and searchable.
I personally think a relational database is a fine tool for this problem, but lately I've been looking at RDF for things and I think RDF might be an even better choice, since it's really designed for metadata description, ontologies (like music categorization) and graphs. I think it would turn out to be a ton of work, but I think it would satisfy many of the requirements.