Wikipedia is probably the last place you should take legal advice from. Also, that article says absolutely nothing about the legality of the game, nor does it make any such implications.

1. It's only really legal if Nintendo gave permission. Otherwise, the creator is only safe until Nintendo decides to sue. And even if the court did declare it as legal (which I highly doubt they would in this case), the cost of the legal battle would sink the creator.
2. Sure, that's perfectly legitimate. There's no guarantee you won't get any cease-and-desist letters though. They may or may not be valid, and you may or may not be found to be legally safe, but you'd just have to decide how you're willing to respond to such a letter if you get one and you feel you aren't violating any laws.
3. Sure, I guess. You can ask whatever you want.

Obligatory disclaimer: IANAL

The issue that people seem to be confused by is the notion that they aren't infringing on the IP if they don't make any money. That is a completely, 100% false notion. Infringement is infringement whether for gain or not.

Fan-made projects exist solely by the good graces of whomever holds the IP. They might tacitly allow such works by simply not acknowledgement their existence, or they might simply be unaware of the work. Neither of those things offers any sort of guaranteed, long-term protection. Many firms will simply C&D all offenders, because carpet-bombing fan-games is far easier, cheaper, and less risky that granting official licenses, or monitoring what's being created.

As for what portions of a game can and cannot be protected:

• The concept of a game cannot be protected -- you can make as many games as you want about plumbers who smash things with their face.
  
• The code itself is protected by copyright, but you only violate copyright by duplicating said code -- in other words, you looked at their code and replicated it, or used their code verbatim somehow.
  
• The code itself could conceivably contain algorithms that are patented, which would be protected -- If the algorithm is core to the game in some way, you'd have to figure out an alternative implementation that achieves the same thing, and it can't be a trivial transformation of the original algorithm.
  
• Artistic elements -- graphics, sound, music, level design, etc -- are protected by copyright at a minimum. You can't replicate these things verbatim.
  
• Some artistic elements that are unique and highly recognizable are also protected by trademark -- trademark protects firms from replicas that are meant to pass themselves off as the original -- You can make graphics for a blue plumber that likes to jump on tortoises just fine, but he better not have a mustache, be named "Nario", and speak with an Italian accent. Trademark is essentially about counterfeiting, its still a violation even when you change small things if the purpose is to deceive customers, or otherwise mooch of the good name of the authentic item.
  

That list is a broad generalization of the various forms of protection that are involved, but by no means exhaustive -- and of course, I am not a lawyer so don't take this as official. Ultimately its you who are responsible for steering clear of legal trouble.

The best advice I can give you is this: If you want to do these things, make a game that's "inspired" by those other games, but don't copy or try to ride on the success of other peoples' hard work. It's a dick move, don't be a douche-bag.

So, even parody games are illegal?

IANAL.

Parody falls under fair use in some jurisdictions, Being right however doesn't protect you from getting sued, it only increases your chances of winning if you decide to fight it out in court. (Also there is a huge difference between making more or less obvious references to other peoples IP and copying their IP)

Freeware and opensource fan games are less likely to be sued due to the potential bad press the IP owner might recieve by doing so but they're not immune to it and some companies are far more likely to sue than others. mari0 is infringing on both trademarks and copyright (graphics are straight SMB rips it seems) and could thus most likely be shut down whenever Nintendo feels like it. (Valve will have a harder time shutting it down though, but they could probably force them to change the logo)