[Neithan]

Well I still haven't had time to look through all of the links provided but I feel the need to add a couple of comments.

It seems logical that if members of the Fellowship, who have just seen a Balrog up close and personal, mistake a flying creature for a Balrog, Balrogs must a) have wings and b) be capable of flight.

Wait a minute, it's not as simple as that. Gimli didn't mistake it for a Balrog, he said that it reminded him of the shadow of the Balrog.

I think that Balrogs could've had wings if they chose but didn't have wings so they couldn't fly but if they did they still couldn't fly unless they wanted to fly in which case they could but only if they had had wings but they didn't have wings since they couldn't fly.

An interesting quote! This is even more confusing than Bilbo's farewell speech (intentionaly I am sure), but it does seem to say that they didn't have wings. The fact that he says that they could have had wings if they wanted does prove that they weren't given bodies by Morgoth though.

My theory is based on my belief that the Balrogs retained their ability to change shape, though. If someone can prove that they lost this ability, my point is voided.

Well there is quite a bit of evidence that they had lost this ability. For one, they had been in that form for a very long time. Also, as I said before if they still had this ability they could not have died by falling off of a cliff. For more information on the subject try here
Edit: Oops, the last post was finished as I was making mine which is why I say some of the same things.