Uh, let's not forget the pinnacle of Nintendo online gaming; Mario Kart Wii. It works perfectly in my mind. It can be done. Plus NSMBW won't being using crazy stuff like the Havok engine to produce realistic physics.
Mario Kart Wii's online mode works entirely differently than Super Smash Brothers Brawl.
First off, when you play an online game, position data is the only data that's transferred over the Internet. Therefore it doesn't matter what kind of graphics, sound, physics engine, A.I. script, etc. that a game uses, it doesn't affect the amount of data transferred.
In Mario Kart, each player does not need to be perfectly synced up, so you don't really notice the lag if you aren't paying attention. The game tracks the position of where each player is on the course, and will "guess" their position based on their last known velocity and direction of travel. Sometimes you'll notice that a player will fall off a cliff, but then appear right in front of you as if nothing happened. Sometimes people will drive right through items and obstacles without hitting them. That was them lagging. Items are the same way. Red shells take a few seconds prior to contact. Bananas may not be exactly where you set them for someone else's perspective. One shell can hit two players if they're close enough.
Animal Crossing also works similarly.
New Super Mario Brothers Wii can't work this way. All players need to be perfectly synced in time with enemies, moving obstacles, and items like coins. Otherwise, two players could defeat the same enemy, grab the same powerup, or other such double-up effects. Also, a lagging player could inadvertently knock another player off of a cliff, or otherwise interfere with them. Since the game is a side-scroller, the environments are ever-changing, which would cause even more problems.
Miyamoto said it couldn't be done. No offense, but I take his word over anyone here.