@Coldkilla
Go with option #4. That is contact the publisher for replacement keys, they may give them to you if you provide proof of purchase of your game, but then they may not!
As DABhand has already said, yes it is illegal to download keys.
Please read the
Forum Rules before asking any other questions.