Neural networks - Find most similar images
I don't think that a high level architecture as such is the best fit but it rather depends on many factors and details. From what I am aware of the first approach is promising especially when extended by additional steps as done in the TiefVision:


An additional bounding box network is used to discriminate the relevant part of the image from the rest
The feature vectors are not simply compared directly but rather used to train a comparison network using triplets (learning similarity based on feature vectors and examples for more and less similar instances).


This work is a lot more recent (2016/17) than what you posted and comes with a nice tool set and a more detailed paper.

Why using triplets aka Deep Ranking?

As stated in the comments: Why should one use triplets for image similarity instead of learning feature vectors and calculate their distance? Triplets are a way of formulating the similarity question as a learning problem instead of learning feature vectors that basically do not care for similarity. This approach makes especially sense in cases where human-perceived similarity is important, which might differ from machine perception.

Triplets work like this: You provide 3 images. One to compare to, one similar (close) and one not so similar (distant) image. This is your training/test/validation data. Training your network on those samples and predicting the correct order (classify similar from non-similar images) overall lets the network learn how to order images based on their similarity. 

All in all this approach is comparatively complex. It might be overengineered but you also asked for the best way to do this and Deep Ranking achieves very high precision values.