It shouldn't. A system format while connected to the internet requires your NNID password and should mark it as removed from the system, which means it should be free for adding to the other system (it's the scenario for if you eg decide to sell your 3DS , then decide to buy another one later). But if that doesn't work , yeah you'd have to call Nintendo and get the NNID reactivated.
that doesn't work from experience.
even if you system format, the NNID can't be used on a different system unless you do a system transfer. i tried that several times and my NNID stays linked to the same 3DS even after the system format.
calling Nintendo is the only option to move the NNID from one system to the other without system transfers.