As is well known, exact probabilistic graphical inference requires a triangulated graph. Different triangulations can make exponential differences in complexity, but since finding the optimum is intractable, a wide variety of heuristics have been proposed, most involving a vertex elimination ordering. Elimination always yields a triangulated graph, can produce all edge minimal triangulations, and can also produce triangulations having the smallest maximal clique size. In this paper, we show that there are cases of practical importance where the optimal triangulation is unobtainable with elimination. Specifically, we show that real-world models with deterministic dependencies exist where the best elimination-based triangulation can have an unboundedly larger state space than the optimal triangulation. We present new methods that, unlike elimination, can generate optimal state space triangulations for such models, and give results for both real and randomly generated graphs. We also give an algorithm and correctness proof for determining if a triangulation can be obtained via elimination, and give a new proof that the decision problem associated with finding optimal state space triangulations is NP-complete.