If you still have the receipt then email them with pictures, I had to do a similar thing when they banned my UT2004 cd-key for who knows what reasons. I emailed them pictured of me holding the game and took pictures of the actual booklet that contained the cd-key all was fixed after that.
You're probably **** if you don't have the CD key and only have the disc. Some companies will replace the disc for a couple bucks shipping, but I haven't heard of a company replacing a CD key in any situation. If all you're paying for is the "license" to play the game as everyone insists on these forums, there's no reason they shouldn't replace it for you for free (since there'd be no cost to email him a key), but it won't happen. Why? You tell me
When you buy something, then it makes sense you hold on to it. The CD-key is one of the proofpoints (if not THE proofpoint) that you bought the game. If you can prove you bought it, then I'm sure they'll give you another key. Enough said.