Como ya han dicho anteriormente, una cosa es que puedan volar o no y otra que tengan o no tengan alas.

Si no tienen alas difícilmente pueden volar, pero el hecho de que las tuviesen no significaría que pudiera volar.

Sí, Gandalf destruye el puente con un objetivo claro: no dejarle pasar, por lo que Gandalf sabía que no podía volar porque si no poco sentido tendría su acción. Éste y otros motivos son los que me llevan a pensar que los Balrogs no podían volar, pero otra cosa es que tuvieran o no alas. En este último punto no estoy muy seguro, aunque me decanto ligeramente a la opción de las alas por el comentario de Frodo cuando ven al Nazgûl alado.