I realize you said you don't want interpolation, but have you considered interp2 with the 'nearest' method? It really seems appropriate here...
Assuming you have a coarse 2-D grid X_coarse, Y_coarse with data V_coarse, and a fine 2-D grid X_fine, Y_fine with data V_fine, you could use something like
V_compare = interp2(X_coarse, Y_coarse, V_coarse, X_fine, Y_fine, 'nearest');
then compare V_compare to V_fine. (Obviously, you could also swap all of the _fine and _coarse variables if you wanted to compare the other way around.)
Note that there are equivalent functions interp1, interp3, and interpn which support the 'nearest' method, if your grid isn't 2-D.
If the default Matlab interp family isn't fast enough, there might be faster implementations on the File Exchange. You might also look into Matlab's griddedInterpolant class with the 'nearest' method, if you have a fairly recent version.
Otherwise, if you're truly opposed to a 'nearest' interpolation scheme, you're probably stuck trying to use a k-D tree search algorithm.
Does the interp function meet your requirements?
--Andy
