An adaptive remeshing algorithm has been developed for multiphase flow simulations using the moving-mesh interface tracking (MMIT) technique. The edge-swapping algorithm uses the Delaunay criterion (in 2D) and a dynamic programming technique (in 3D) to maximize the quality of mesh primitives surrounding edges in the mesh, and performs local remeshing to minimize interpolation errors. Edge bisection and contraction operations are also performed to adjust the mesh resolution around important features like fluid-interfaces, driven by a local length scale estimation algorithm that is efficient and easily parallelized. Flow-field interpolation after reconnection is achieved using a conservative, second-order accurate remapping scheme that can be extended to arbitrary mesh pairs. To minimize the number of mesh reconnection operations, vertices in the mesh are also moved in a manner that optimizes the quality of cells at every time step, using a spring-analogy based Laplacian smoother for surface meshes, and an optimization-based smoothing approach for interior points. To facilitate the simulation of large-scale problems, all smoothing and reconnection algorithms in this work have been parallelized for shared- and distributed-memory paradigms. This approach allows meshes to undergo very large deformations which are characteristic of multiphase flows, and the method is versatile enough to extend its applicability to a broad range of problems including error-driven mesh refinement, reciprocating machinery, fluid-structure interation, and wing flapping simulations.