Is the time-consuming bit the one where for each vertex of mesh A you identify the closest vertices in mesh B?

If that's so, one idea for speeding things up is to use a grid like you would on a map (only in 3d, of course, so the grid cells would be cubes instead of squares). First you go through mesh B and for each cell of the grid store the list of vertices in B that it contains. Then when you look for nearest neighbors of some vertex in A, you only need to look at the cell that vertex falls in and possibly its neighbors. If you space your grid cells right, you can be certain enough not to miss anything, but you'll only have to do a fraction of the distance computations.

-- I'm not mad at you, just Westphalian.