One important idea would be to switch to a different algorithm near the end of the simplification. The data structures for a total-order optimization (such as a Progressive Mesh) are probably more efficient near the tail end of the visualization I showed earlier.

Another thing to look at is the order and type of local remeshing transformations that are attempted. Perhaps better efficiency or element quality can be achieved with a different order.

It may be beneficial to consider a sequence of transformations to avoid getting stuck in a local minimum. Multiple operations that temporarily decrease local element quality may be required to remove a particularly bad element.

Topological simplification could be added to the algorithm when it can be determined that the the model contains unnecessary or erroneous topology.