Calem/Serena never use their Fletchling again after their first tag battle w/ you against Tierno & Trevor, so they don't have a Gale Wings Talonflame. People made up stories about it, much like Gary's missing Raticate, but it just never appears in the game again.
And yes, all the NPCs have set Pokemon (excluding some differences e.g. your starter choice, or you hacking to change it).
As for the reason why it has Gale Wings, there's no explanation for it. It just does, and we have to deal with it. If you want an in-game explanation, then I assume the most likely/ plausible reason is that Calem/Serena is the child of veteran trainers, and therefore could've gotten access to a Gale Wings Fletchling via their parents.
Also, you cannot get Fletchling or any of its evolutions in horde encounters.
Serena || Calem