Understanding the migration history of cancer cells is essential for advancing metastasis research and developing therapies. Existing migration history inference methods often rely on parsimony criteria such as minimizing migrations, comigrations, and seeding locations. Importantly, existing methods either yield a single optimal migration history or are heuristic algorithms without guarantees on optimality nor comprehensiveness of the returned space of migration histories. To address these limitations, we introduce MACH2, a method that systematically enumerates all plausible migration histories by exactly solving the Parsimonious Migration History with Tree Refinement problem. In addition to the migration, the comigration, and the seeding location criteria, MACH2 employs a novel parsimony criterion that minimizes the number of clones unobserved in their inferred location of origin. MACH2 allows one to specify the order of criteria to include during optimization, allowing users to adapt the model to specific analysis needs. MACH2 also includes a summary graph and MACH2-viz to explore the solution space and identify high-confidence migrations. Using simulated tumors with known ground truth, we show that MACH2, especially the version that prioritizes the new unobserved clone criterion, outperforms existing methods. On real data, MACH2 detects uncertainty in non-small cell lung, ovarian, breast, and prostate cancers, and infers migration histories consistent with orthogonal experimental data.