So I just had another thought, related to my earlier 'find all the items in the building' idea; would it be feasible to make a game where, every time you start a new game, the locations of certain key items are randomised? So like a semi-roguelike; the layout of the map is always the same, but you'll need to learn all the locations of where items might appear because they'll never appear in the same place twice.
And related to that, if you had a fairly short game with multiple endings, would there be a way for the game to acknowledge which endings you've gotten, perhaps if you wanted a special bonus ending that you can only get if you've gotten all the others?