@RAV: I think you might be straying a little from your mark lol. You hit it on the head before with the "when something isn't more than the sum of it's parts" and I think that applies to any situation of the uncanny valley.
This mario peice follows suit with that thinking -- everything else about the image is cool, and even somewhat believable -- except the eyes.
All the rest could really just be a deformed head, all the hair and bone structure, everything, is fairly believable, but the thing that breaks the believability is that no spherical eye with the shape it's trying to describe can physically fit in those sockets. It's THAT part in which you find the uncanny valley in this image -- the eyes don't fit with the rest of the parts, and so the parts never create something more than just their sum, which lends an opening to the disturbing uncanny valley where your mind would normally just say "cool, a realistic-looking mario!" to "omg, wtf did they do to that guy's skull??" by simply screwing with the physics of the eyeball sockets (most likely unintentionally).
To further my point, I saw the Jessica Rabbit this guy did and that didn't hit the uncanny valley for me. In case any of you've not seen it:
The shape is obviously in the style of the cartoon, but it looks believable. Physics-wise, it's very believable. Your brain doesn't say "Whoa!! WTF is that FREAK!!??" due to the (should-be obvious) deformities, but instead it says "Nice!"
Keeping science-heavy stuff out of an art discussion, the reason it doesn't strike that "gross/ugly/freaky/insertnegativefeelinghere" that is typical of the uncanny valley is because our brains base it on what we remember a woman and a human to look like, and due to the curvature and other features that suggest "hot" woman as well, we perceive the image as pleasurable to look at. Not sure if this is the same for women, but I would think it's at least not a negative experience for them since nothing looks "off" in the image (albeit improbable, it's not impossible -- unlike mario's skull.)
On the other hand, a muscle-baby (as we've come to know it as more of a muscle-infant) is in most ways impossible since we know a human baby is unable to achieve that kind of physical form or physique. That little kid in the video in the muscle-baby topic, on the other hand, was not an infant, so it was still believable, despite still being a bit uncanny at times since most of us couldn't conceive of a real kid with those kind of muscles, despite seeing it in that video, and it's likely your brain was still thinking along the lines of "gross. think of the stretch marks that kid's going to have! what a horrible parent for forcing him to do that sort of thing!" or something else a bit on the negative side instead of "props to that kid! what an amazing sense of determination that kid must have!" or the like, as is usually associated with the uncanny valley thing. The bottom line is, even in the case of the older kid, the muscles still don't fit the whole of what our minds tell us a kid should be able to look like physically, so it becomes "uncanny" rather than just "real cool".
So, to answer your question, it's the latter -- you see uncanny when you see something that tells you it's something that your eyes are almost 99% sure they believe, but you know there's still that 1% of something about it that doesn't fit with what you know is true somewhere deep down, so your brain kicks it back and the thing becomes uncanny -- which is what makes the mario picture, as I mentioned before, so disturbing.
---
Returning to the topic though:
I think since there's a lot of experimentation going on in game styles and visual styles, the theory on what works visually for games is going to become about as vague as art itself much sooner than later. However a lot of interesting things will come about in that discussion on visual style in the form of statistics, virility, and other such things that are decreasingly relevant with every new generation of gamers. At the same time though, some long-established ideas about such things will be broken too. As with pixel art, what used to be about blurry blobs of light on the screen that vaguely represented something on old CRT tvs, is now about the crisp, well-placed, precision-styles that only pixel art can give you. The evolution of pixel art as a medium will trend-in and trend-out as television and the ways in which we watch it as well as the stuff we watch does.
As always, people enjoy it when new life is breathed into an old medium. Pixel art is no different.
Just like RAV mentioned in a previous post, you've got to stick to what you're going for in a project's visuals. If you stray, then you better make sure you've got a clear and harmonious way in which to do it that doesn't go against the rest of your visual mechanism as a whole. And if it does, you better find a way to make that work by adding or removing elements (be it visual styles or game mechanics that don't fit).
I've personally always been about the idea that game design should be about the feeling the player gets when playing your game, rather than the mechanics or the visuals themselves. Many people don't seem to agree with me. But it's a big motivator for me to play your game -- does it make me feel relaxed, energized, powerful, etc., and does this go with the gestalt of the game itself, visuals, mechanics, intent, everything? If so, you've got the makings of an amazing, visually-appealing, and fun game that can become a classic. Even games with super-simple "realistic" pixel characters as Cyangmou pointed out can look cool when they move around and do cool things. Not sure if they can be a "classic" by just focusing on theatrics, but I'd love to see more modern games with excellent gameplay AND theatrics (wouldn't we all?)
A lot of indie games created nowadays are defined by their visuals, and not the other way around. Though, as mentioned before, that's because it's harder to stand out without a memorable look. At the same time though, as the AAA developers are seeing, it's hard to keep a following with surface beauty alone.
I think a unique look is made memorable by great gameplay. As mentioned above, that fencing game, has no details, programmer graphics, etc., but its look is memorable because it seems to play amazingly well. I think even if it had musclebabies fighting with fencing swords, it could still pull off being visually memorable, despite the (probably better) muscle-baby graphics and the uncanny valley that inevitably goes with the creep factor. That may just be me though. ;P