The spatial resolution of microbathymetry maps created using robotic vehicles such as ROVs, AUVs and manned submersibles in the deep ocean is currently limited by the accuracy of the vehicle navigation data. Errors in the vehicle position estimate commonly exceed the ranging errors of the acoustic mapping sensor itself, which creates inconsistency in the map making process and produces artifacts that lower resolution and distort map integrity. We present a methodology for producing self-consistent maps and improving vehicle position estimation by exploiting accurate local navigation and utilizing terrain relative measurements. The complete map is broken down into individual "sub-maps'', which are generated using short term Doppler based navigation. The sub-maps are pairwise registered to constrain the vehicle position estimates by matching terrain that has been imaged multiple times. This procedure is implemented using a delayed state Kalman filter to incorporate the sub-map registrations as relative position measurements between previously visited vehicle locations. Archiving of previous positions in a filter state vector allows for continual adjustment of the sub-map locations. The terrain registration is accomplished using a two dimensional correlation and a six degree of freedom point cloud alignment method tailored to bathymetric data. This registration procedure is applicable to fully 3 dimensional complex underwater environments. The complete bathymetric map is then created from the union of all sub-maps that have been aligned in a consistent manner. The method is applied to an SM2000 multibeam survey of the TAG hydrothermal structure on the Mid-Atlantic Ridge at 26(°)N using the Jason II ROV. The survey included numerous crossing tracklines designed to test this algorithm, and the final gridded bathymetry data is sub-meter accurate. The high-resolution map has allowed for the identification of previously unrecognized fracture patterns associated with flow focusing at TAG, as well as imaging of fine-scale features such as individual sulfide talus blocks and ODP re-entry cones.