Ah, so maybe they did have wings...

[Galorme]

I liked what someone said about this a while ago

Balrogs are Fallen Angels. They can do whatever the hell they want

Not entirly accurate but a good line after all. If they wanted to fly then they could have chosen to at the beggining, but after a while their form was fixed. So they could have chosed to have wings when they made their bodies. I suppose what you have to decide is at which point were they were Fixed, when they could no longer change their forms. Was this at some point during the age of stars or before? Or was it during or after the First Age?