In my 20 or so manual tries of billboard top 100 songs and some other random ones, Genius is top 1-2 in results, so they might have recovered fine in the SEO sense...

That is a really interesting example. They had the best product by far. Google penalizing them is almost like penalizing its own users because they provide a much better product for lyric searches, in my own opinion. Every other lyric site before them was generally full of spammy ads with no added value, but Genius actually tries to add to the experience. Some songs more than others, but still a world away from the old lyric sites.