Plan execution in unknown environments poses a number of challenges: uncertainty in domain modeling, stochasticity at execution time, and the presence of exogenous events. These challenges motivate an integrated approach to planning and execution that is able to respond intelligently to variation. We examine this problem in the context of the Europa Lander mission concept, and evaluate a planning and execution framework that responds to feedback and task failure using two techniques: flexible execution and replanning with plan optimization. We develop a theoretical framework to estimate gains from these techniques, and we compare these predictions to empirical results generated in simulation. These results indicate that an integrated approach to planning and execution leveraging flexible execution, replanning, and utility maximization shows significant promise for future tightlyconstrained space missions that must address significant uncertainty.