Interactive storytelling (IS) systems are an emerging class of interactive entertainment applications with an emphasis on narrative aspects. One of the approaches used to develop IS applications is based on planning algorithms. This article describes two mechanisms that can be introduced to planning-based IS in order to solve two problems that are inherent in this approach. The first is a technique to control the pace at which a story evolves, so that the story that is generated follows a specific tension arc. The second is a method that makes it possible to avoid dead-ends in a story by intervening to justify previous events. These mechanisms help to produce a more enjoyable user experience, since their use tends to result in stories with higher narrative consistency. Results from experiments with users suggest that the proposed mechanisms improve both of the aspects addressed by this article.