De manera local puedes crearte el gamertag que quieras. Es mas la propia consola suele ofrecer varios aleatorios.
Si la asignas a una cuenta de correo para tener lo que es ya el gamertag del live como tenemos todos, la consola accede a internet y mira si el gamertag esta cogido por otro jugador o no.
Si esta cogido la consola te da 5 variantes disponibles de ese nombre ya pillado, o bien te deja una ultima opcion para que vuelvas a intentar ingresar un nuevo gamertag a tu gusto que volvera a ser comprobado en su disponibilidad.