This was not greyhat. This was blackhat. Paying money for inbound links on keywords that trasnfer page rank (don't include NOFOLLOW) has been blackhat for a LONG time.
It was Panama hat. Rap Genius did not pay money, they offered a tweet. In a crude and obvious enough way to be a little scheme-y. Which unfortunately for RG was picked up in the media.
"even I was scratching my head to figure out if this was actually a Google violation or not. Rap Genius’s apology post had the company deciding itself that maybe it violated guidelines that links should be “editorially placed." - Danny Sullivan.
Paying with a Tweet from an account with a large number of followers (which definitely has value) instead of money is still paying. At best, it's basically a link exchange, which is also not allowed.
"even I was scratching my head to figure out if this was actually a Google violation or not. Rap Genius’s apology post had the company deciding itself that maybe it violated guidelines that links should be “editorially placed." - Danny Sullivan.
At least now we know. This is blackhat.