What Distance Measure Is Proper for Image Patches?
Well, You're asking on one of the most researched topics.  

There is no 1 "Right" answer.
Many models have been suggested and many of them works pretty well.

In the Non Local Means they use Euclidean Distance.
Later revisions on the idea used Mahalanobis Distance.

Others are using different norm, other use Learned Dictionaries.  

Some use features or transformation of the data.

I think the best method depends on the image (Or set of images) and the usage (Denoising or something else).