In order to make a new NNID on a 3DS, you have to format to remove the old one, right? Here's the kicker: in order to format, you have to connect to the internet to verify your NNID status. If it's banned, you cannot format the system. This happened to a guy at Gamefaqs who bought a used 3DS and it had a banned NNID on it, and he couldn't put a new NNID on it.
I don't see why you can't format emunand again using gateway. As long as sysnand and emunand are unlinked it should be possible.