Because models used to represent the Gibbs energy of mixing are typically highly nonlinear, the reliable prediction of phase stability from such models is a challenging computational problem. The phase stability problem can be formulated either as a minimization problem or as an equivalent nonlinear equation solving problem. However, conventional solution methods are initialization dependent, and may fail by converging to trivial or nonphysical solutions or to a point that is a local but not global minimum. Since the correct prediction of phase stability is critical in the design and analysis of separation processes, there has been considerable recent interest in developing more reliable techniques for stability analysis. Recently we have demonstrated a technique that can solve the phase stability problem with complete reliability. The technique, which is based on interval analysis, is initialization independent, and if properly implemented provides a mathematical guarantee that the correct solution to the phase stability problem has been found. In this paper, we demonstrate the use of this technique in connection with excess Gibbs energy models. The NRTL and UNIQUAC models are used in examples, and larger problems than previously considered are solved. We also consider two means of enhancing the efficiency of the method, both based on sharpening the range of interval function evaluations. Results indicate that by using the enhanced method, computation times can be substantially reduced, especially for the larger problems.