Application rejected due to 8.5: Use of protected 3rd party material

Question

I have developed a lyrics finder application, spent more than a month adding and organising them in a database, yesterday, Apple review team rejected my app due to use of protected 3rd party material.

The use of materials copyrighted by a third party requires documented evidence of your right to use such content in your application.

What should I do in that case, should I contact every artist telling him if I can add his songs lyrics in my app?!?! What do they mean by documented evidence? I feel that they're requesting an infeasible thing. I can't accept that all that effort made during more than a month is vanished! Do you faced such rejection before? And is there a feasible thing to do? Here is 2 screenshots of the app(sent/chosen by Apple review team):

And what about this one: https://itunes.apple.com/us/app/lyrics-lite-lyricfind/id310626563?mt=8 And that one: https://itunes.apple.com/us/app/lyrics+/id376969803?mt=8

Isn't a misjudgment ?!

Answer 1

Having a quick look at Wikipedia reveals that you need a license for publishing them:

Currently, there are many websites featuring song lyrics. This offering, however, is controversial, since some sites include copyrighted lyrics offered without the holder's permission. The U.S. Music Publishers' Association (MPA), which represents sheet music companies, launched a legal campaign against such websites in December 2005, the MPA's president, Lauren Keiser, said the free lyrics web sites are "completely illegal" and wanted some website operators jailed.

So this is not a misjudgement from Apple, they even protect you in some way from being sued by a random law company (for using copyrighted material without permission).

Regarding other lyrics apps on the AppStore: I assume they have a license. At least LyricFind does, as you could obtain a license for publishing lyrics from them.