For people wondering the legality, Joystiq's "go-to-guru" for legal matters, Mark Methenitis, put this on Joystiq:
"According to Methenitis, GameStop's actions were "probably legal." The packaging of the PC version of Deus Ex: Human Revolution makes no mention of the OnLive promotion and, as such, GameStop can't be accused of false advertising or deceptive trade practices. "From the consumer angle," said Methenitis, "there's not much."
The corporate angle, on the other hand, could be a different matter. If there was an agreement between Square and GameStop prohibiting such a promotion, GameStop could be "completely justified" in its action. Absent of such an agreement, "OnLive and or Square may have a claim against GameStop for tortious interference or something else based on the activity." That said, without any details as to the distribution agreement, the legal implications of GameStop's actions remain murky."
So they may be legal, but let us not forget the court of public opinion is far less lenient.