I never personally had to message NA support (JP Support is actually a pain since there's an actual form and all), but I have heard other's experiences. From what I've gathered out of what they told me, they've done it as-
> Explain what happened (Uninstall, Phone Transfer acting weird and unsure the Code is still intact, lost the Code, etc.)
>>> Do *not* ever mention emulators, if there was one involved. I had a friend who decided to fess up (and explained why - Their Phone/Tablet didn't have the power to run the game, whereas their computer had the power to run it) and the guy over at support was nice enough to just give a slap on the wrist and say 'Don't do it again. If I catch you on Emulators with another request, your account is toast.'
> Fill out the form/format.
>>> If you have an IRL friend who has your Friend Code, ask them to pull it up so that you can be as detailed as possible. I'm not sure with NA, but JP support is especially picky about this. I sent them one over New Years in hopes of obtaining my original JP account again (I restarted shortly after New Years last year due to having lost said account) and accidentally gave the *new* account's name with the old one's info. They only found the new account and went "Okay, something's weird here. Re-fill in these parts and also list possibilities on the Master's Name. If you can find the Friend Code, send that, too." (Not as nice as this, it was actually worded a lot more roughly).
-Pray to Saber that you can get it back within a few hours.
Long response, heh, sorry. Good luck on getting your account back!
Edit: Formatting. Apparently, GP doesn't like using Spaces as an alternative to being unable to tab.