Domain models for sequential decision-making typically represent abstract versions of real-world systems. In practice, such abstract representations are compact, easy to maintain, and afford faster solution times. Unfortunately, as we show in the paper, simple ways of abstracting solvable real-world problems may lead to models whose solutions are incorrect with respect to the real-world problem. There is some evidence that such limitations have restricted the applicability of sequential decision-making technology in the real world, as is apparent in the case of task and motion planning in robotics. We show that the situation can be ameliorated by a combination of increased expressive power—for example, allowing angelic nondeterminism in action effects—and new kinds of algorithmic approaches designed to produce correct solutions from initially incorrect or non-Markovian abstract models.