BS!
It should be a huge sticker you can't miss on the inside of the case, if it's a legit copy. Possibly placed on the manual, but mine is on the box.
It should be obvious, even to them, when a game itself says "Product key please" it needs a freaking product key.
Yep--big sticker in the box---it's impossible to miss.
BTW--mine game came in a standard black DVD case with appropriate labels, manuals and codes for additional stuff like the classic pack, not in a box.
Sounds a little fishey to me as well.