The people who are claiming that do not know anything about SEO. They're pulling figures from fresh air. For instance, in the case of JC Penney[1] it took them 90 days to recover from their penalty but it took Interflora[2] 11 days etc.

The penalty is applied until, the site fall backs into the Google Guidelines[3]. Google actually helps Webmasters to get their site back in line with their guidelines through informing them what type of penalty[4] it is. For instance, if it is a link penalty like Rap Genius has, Google shows example links within Webmaster Tools (usually 3 of them) to provide insight, on links which Google considers to be falling outside of those guidelines.

However, the links which are going to be affecting Rap Genius were predominantly because of the "tweet-for-links" system, the identification and removal of links should be relatively quick and straightforward.

[1] http://searchengineland.com/90-days-later-google-lets-j-c-pe...

[2] http://searchengineland.com/interflora-gets-google-rankings-...

[3] https://support.google.com/webmasters/answer/35769?hl=en

[4] https://support.google.com/webmasters/topic/2604771?hl=en&re...