Typical of Best Buy.
Sell you a machine, attempt to restore it for you and lose all of your data in the process (because they truly are terrible at this sort of thing) and then tell you that it's a shame and too bad you will never see it all again.
However, if they built it and it's still under warranty they need to and have an obligation to replace it to the state it was in when you walked out of the store with it originally.
Barring that... CyberLink is usually pretty helpful. If you can somehow PROVE to them you had a legitimate copy, they are more than happy to assist you in recovering your key(s).
Good luck with this. I hope it all works out for you.