IANAL.So, even parody games are illegal?
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)