[Gordis]

Going out on a limb here (while waiting for the Christmas fudge to cool): The thought comes to mind that whatever the creature's real name might be, the original critter that eventually became the Winged Nazgul Mount™ could have been Melkor's attempt to parody his brother Manwe's Eagles

I don't think so. I believe Morgoth's response to Manwe's Eagles were definitely the Dragons: Morgoth had indeed put a lot of work in Glaurung, Ancalagon and the rest of them and got impressive results.

Undoubtedly originally (before Sauron's intervention) the FB were much smaller than the Nazgul Mounts™: although maybe related to cold Drakes, they were some small flying carnivorous critters living under the Shadow of Morgoth.

When somwhere a shadow lies, the local fauna tends to become creepy (i.e. Mirkwood). I don't think Morgoth paid the FellBeasties any special attention, like Sauron hardly specifically bred black squirrels of Mirkwood: they were too insignificant.

As for how the original FellBeasties looked like, I am tempted to post a small excerpt of a fanfic Mountain guardswhere a nest of wild FellBeasties is described. I think the author was very close to the target in this description:

From a fanfic by Malicean: A hiss like a live coal hitting water. A very angry coal – and it brought friends. The Uruk is lucky to loose merely the tip of an ear and a handful of stringy hairs when a score of greedy jaws shoot from the rock face on skinny necks. Pu-sha-skoirs. Winged-Maws. Fellbeasties. Perfect stock for breeding a grisly airborne steed – if you’re a Ringwraith with a couple of millennia on your hands and nothing better to do.
If you know where the colony is, you simply stay out of reach, and they’ll do nothing but hiss and spit. They prefer dead meat to those who might fight back – but if opportunity marches straight into their jaws… Unlike their giant cousins, fellbeasties can’t bite you in halves, but they can take off a hand, a foot or half of your face, whatever they get hold of. And perched at the entrances of their rocky nests, necks writhing snakelike and wings spread for full display, they look more than ready to attack.

The original Fellbeasties (little creatures prone to evil) likely lived somewhere near Utumno and Angband. When this region had sunk, they probably didn't fly far, but continued to live in the nearest "forgotten mountains cold beneath the Moon"
Now which mountains would that be? - If we believe the maps of the First and the Second Age by K.W. Fonstad, Utumno must have sunk in the place where later there was the Ice-bay of Forochel. Just have a look at the site of Utumno on these two maps:First Age Second Age
In the Third Age the nearby cold mountains were known as the Mountains of Angmar, where the Witch-King's fortress of Carn-Dum once stood. Very likely the small fellbeasties felt quite comfortable under the Shadow of Angmar and maybe they were indirectly referred to in the description of Angmar in App. A:

the realm of Angmar arose in the North beyond the Ettenmoors. Its lands lay on both sides of the Mountains, and there were gathered many evil men, and Orcs, and other fell creatures.

Anyway, it is quite probable, that although this component of Angmarian fauna originally had been of little use to the Witch-King, later he told Sauron about the critters and advised to bring a few of them to Mordor for experiments. (The Witch-King's involvement in the FB project is specially noted in "the Hunt for the Ring , RC). Sauron, after his failure to enlist Smaug to his side and the dragon's destruction, likely sought other flying creatures to work with.
I guess it was not easy to find the remaining fellbeasties in the mountains of Angmar, but eventually, the search parties returned and brought to Mordor the last remaining brood, maybe 30-40 years before the War of the Ring.
By 3018, Sauron managed to make them grow "beyond the measure of all other things that fly", but I think the brilliant idea to give them as steeds to the Nazgul came at the last moment, after the Nazgul lost all their horses but one at the Ford of Bruinen.