I suspect it has to do with the lower resolution. I'm using nearest neighbors interpolation for resizing images and have noticed similar behaviour before. Would be great if you can try with higher resolution versions(preferably > 200px) of the same images and let me know the results.

A closer inspection of the results actually shows some of the results aren't that bad a match. Results ordered 1, 4, 5, 7 and 7 in particular vaguely have the same outline as that of the query image. If I have to score this result, I wouldn't give it more than a 3 out of 10 for sure.