Google punished them appropriately. They fucked themselves.
99% of lyrics sites are utter trash littered with popups, redirects and extremely obnoxious ads. Genius was the first lyrics site I ever saw that broke that mold.
Sure, they also broke Google's arbitrary rules, but they had a better product that genuinely deserved to be at the top of the rankings. I still wince when I click on a link to any other lyrics site.
The lyrics licensing industry is absolutely brutal, and I will be pleasantly surprised if anyone that isn't owned by a music publisher is able to succeed in this market.
How on earth were the rules arbitrary? These guys were exploiting and abusing backlinks to boost their page rank.