Total body photography is used for early detection of malignant melanoma, primarily as a means of temporal skin surface monitoring. In a prior work, we presented a scanner with a set of algorithms to map and detect changes in pigmented skin lesions, thus demonstrating that it is possible to fully automate the process of total body image acquisition and processing. The key procedure in these algorithms is skin lesion matching that determines whether two images depict the same real lesion. In this paper, we aim to improve it with respect to false positive and negative outcomes. To this end, we developed two novel methods: one based on successive rigid transformations of three-dimensional point clouds and one based on nonrigid coordinate plane deformations in regions of interest around the lesions. In both approaches, we applied a robust outlier rejection procedure based on progressive graph matching. Using the images obtained from the scanner, we created a ground truth dataset tailored to diversify false positive match scenarios. The algorithms were evaluated according to their precision and recall values, and the results demonstrated the superiority of the second approach in all the tests. In the complete interpositional matching experiment, it reached a precision and recall as high as 99.92% and 81.65%, respectively, showing a significant improvement over our original method.