This sounds like a wonderful idea, but it requires something that very few major game-making companies are willing to do - allow the player to be as imaginative as they can. There are so many ways a person could go around achieving the target that it would have to truly be free-roam. Graphics would have to be good all-round, and not just a few brilliant panoramas (sp?) to show off. Also, your past choices could cause the task to become impossible, which would get it some bad reactions.

Now, I'm not saying that such "risky" games aren't being made any more, but if we are to see this, I'd expect it to come from an indie developer.