I’ve assumed that flamenco has always been a Spanish word for a dance, but Michael Quinion in his excellent newsletter (recommended reading) says:

A direct Flemish connection is actually more plausible. From 1579 to 1700 Flanders was part of the Spanish Netherlands and Spanish fighting men were based there. This is why one sense of “flamenco” in Spanish is of a soldier. It has been suggested that some of them were Roma and that on their return to Spain they were given special dispensation to live where they wanted and take any occupation they liked, unlike other Roma, who continued to suffer severe legal restrictions. In consequence, some Roma families of Andalusia were given the title of “los flamencos”, the Flemish ones (George Borrow mentions this in Zincali) and the art form was taken from this.

Any further suggestions?

Interesting. OED gives only “Spanish, = flamingo n.” but it’s difficult to see any connection with the bird. (Flamingo itself is cognate with flame). The few flamenco sites I checked tend to side with the Fleming theory, including this one).

Most likely the name Flamenco was chosen as a reference to the indecent, undisciplined Flamencos (the Flemings) from the times in 16th century when the Flemish emperor Charles (El Flamenco) ruled over Spain. It was also the Flemish Charles, crowned as king of Spain in 1516 when the strict and severe Islamic lifestyle still existed in Granada, brought Latin singers or Cantors from Flanders to sing in the Spanish cathedrals, all intended to brighten up the sober Islamic lifestyle. These very good singers were called Flamencos (Flemish). Thus arose the link between cantor and flamenco (coming from Flanders).

This site mentions another theory but marks it as problematic.

Blas Infante, in his book Orígenes de lo flamenco y secreto del cante jondo, controversially argued that the word flamenco comes from Hispano-Arabic word fellahmengu, which would mean “expelled peasant”.  Yet there is a problem with this theory, in that the word is first attested three centuries after the end of the Moorish reign.  Infante links the term to the ethnic Andalucians of Muslim faith, the Moriscos, who would have mixed with the Gypsy newcomers in order to avoid religious persecution.

Today’s bit of irrelevant trivia: what is called in English (I think) a “dark lantern” (a lantern with opaque sliding shutters) is called in Spanish linterna flamenca

These ex-soldiers [Roma] who had served in the army in Flanders against the Flemings then gained the nickname of Flemings (Flamencos) by the surrounding Spanish population (8). This appears to be the most plausible origin of the term Flamenco, a Spanish war veteran of Romani ethnicity. Later, the term was applied to the music played by the descendants of these original Romani settlers. Attempts to connect Flamenco with Arabic words do not stand up to analysis since the term Flamenco appeared long after the end of the Moorish rule in Spain and the expulsion of the Moors. Most students of Flamenco agree that it was the sedentary Roma who developed Flamenco rather than the nomadic Roma. By the time Flamenco became popular outside of Andalusia there were very few nomadic Roma left in Spain.

From this website by a Romani author.