Winged Nazgul- Dragons, winged horses, something else? WHAT WERE THEY.

[Fingolfin of the Noldor]

Wehn I read the description in ROTK, I also thought of pterodactles. The description fits.

Indeed it does:

In response to the question: Did the Witch-king ride a pterodactyl at the siege of Gondor?:

Pterodactyl. Yes and no. I did not intend the steed of the Witch-King to be what is now called a 'pterodactyl', and often is drawn (with rather less shadowy evidence than lies behind many monsters of the new and fascinating semi-scientific mythology of the 'Prehistoric'). But obviously it is pterodactylic and owes much to the new mythology, and its description even provides a sort of way in which it could be a last survivor of older geological eras.