I think it comes down to your point of focus. With peach and peach 2, The eyes change shape quite a bit. Humans notice that much more than other aspects.

In general, I think the "ours" method could benefit by moving the boundaries between colours in and out until they get an average brightness match with the similar area in the nearest neighbour version. A lot of the "ours" images have a higher proportion of black.

Super2xSaI looks better to me at 4x than bicubic, and EPX does an OK job but the others look pretty terrible.

I think the problem is that those sprites use multiple strategies for handling diagonal outlines. Those look fine when the image is blurred together, but when you try to detect the outlines and upscale them, the differences between techniques are exaggerated.