You mention back to Mario, but wasn't Super Mario Bros 2 (aka SMB the Lost Levels) not released to the US because they said US players couldn't handle the difficulty? Or was it more because they could save their games being FDS and we couldn't (no battery backup yet)?
I've always been piss-poor at fighting games, so maybe I'll start giving the Jap versions a go...