I did exactly as you said:
Turn off your 3DS > Take out the mSD > Turn on 3DS without mSD > Format the system from System Settings > Go through setup process >Turn off > Insert mSD >
Now I cant seem to install the gateway exploit anymore...this Exploit Failed: 00000005 c86044cd
-_- kinda going mad now...
Ah gotcha, I got confused and thought you had the same problem as joex11.
Formatting the Sysnand wipes the profile exploit, but you can use your DsTwo to install the Rninstaller again.
I've done that about 5x myself. :|