My suggestion would be something along the lines of "[pool of possible prefixes*]+[3-8 alphabetical characters with the first auto-capitalised, and the rest forced lowercase except possible the 3rd for "McCree" etc]+[pool of possible suffixes*]" (*one or the other) and generate 8 possible options at random just like the 8 character models you can to pick from.
E.g. I type in "Chaos" and it gives me 8 random options like "Bilge-rat Chaos", "Chaos the Mad", "Peg-leg Chaos", "Chaos the Silent"..etc.. and just like IPG I can reroll options until I find one I like.
You should never see someones xbox gamertag whether it is in the in-game chat or when seeing it above ally or an up close enemy, or even on a death message, you only need to see their pirate name while playing the game.
When viewing your own crew in the menu you can still see their gamertag and open the link to their profile as normal, and if you did ever need to report any enemy they could build a feature into the website where while logged into your own account you can see a list of all the pirate names of people you interacted with in the last ~10 sessions that can then link to their gamertags or allow you to report them directly.