Well, their selling of it wasn't illegal, really, just more of a breach of contract.
And yes, you're right. Stay far away from any second-hand game that has CD-key style copy protection. Those second-hand things have a curious habit of their CD-keys being retained by their previous owner (13 year olds think they're being so clever by getting their allowance money back by 'selling' their copy, only to retain their copy on the HD or a burned CD).
I have this thoery that 75% of the gaming industry's problems are caused by 13-year-olds. Maybe it's crazy, but that's my pet theory...
The bargain bin is a far better bet (just make sure it's still shrink-wrapped).
Glad your store cooperated with you, and gave you the new copy you deserved. Legit users should never be inconvenienced.