If the casing wasn't sealed when you got it from the shelf at the store someone may well have just opened it and written down the CD-key while it was lying there.
I know at least one store that does that crap, so the CD/DVD doesn't have to be in it, but I only buy sealed software cause of the CD-key stealing.