If you're generating a mosaic like this one rather than a flat panorama (sometimes called a mosaic), then I guess you need to match by colour and rough image shape. You seem to have the colour matching efficiently nailed with LAB colour and your KD-trees.
To match the rough image shape with the original image patch, I suggest using some sort of wavelet transform on the image for each colour. Use the wavelet of your choice. You could either normalize the frequencies, weight them (lower frequencies are more important to you, and your feature vector already contains frequency 0) and concatenate them onto your existing feature vector. Or, you could transform the patches of the original image and evaluate the correlation. Not sure whether or not you need to choose an orthogonal basis set for your correlation to be scalar product of the results of the transform.
In terms of your distance metric, it might be a good idea to use the L infinity norm on the difference in the RGB colour space, because it would consider black-white, black-yellow, and black-red etc. mismatches to have the same value (the length of the side of the RGB cube), a sensible assertion in terms of human perception of colour.
As your dimensionality gets higher you might need to use a FLANN (if you're not already doing so) for performance. Another technique you can use to artificially reduce the dimensionality of your nearest neighbor search is Locality Sensitive Hashing.
I wouldn't really recommend the original SIFT algorithm for that type of mosaic since it only matches interesting points. Dense SIFT or PHOW (which I guess is what you've read up on), is not something I'd recommend either, since it fundamentally looks at the gradients in small areas of the image, clusters/assigns them into "visual words" and then loses information about the locality of these words by treating the image as (1 or a set of) bags of visual words. It works surprisingly well for matching very similar images, but since you'd lose information about the structure of your image patches, then I wouldn't recommend for this purpose.
A library I'd recommend having a look at is VLFeat.
Best of luck!