The evolution of flagella is of great interest to biologists because the three known varieties of flagella (eukaryotic, bacterial, and archaebacterial) each represent an extremely sophisticated cellular structure that requires the interaction of many different and finely-tuned systems to function correctly.
The primary point in favor of the symbiotic hypothesis is that there are eukaryotes that use symbiotic spirochetes as their motility organelles (some parabasalids inside termite guts, such as Mixotricha and Trichonympha). While this is an example of co-option and the flexibility of biological systems, none of the proposed homologies that have been reported between cilia and spirochetes have stood up to further scrutiny. The homology of tubulin to the bacterial replication/cytoskeletal protein FtsZ is a major argument against Margulis, as FtsZ is apparently found native in archaea, providing an endogenous ancestor to tubulin (as opposed to Margulis' hypothesis, that an archaea acquired tubulin from a symbiotic spirochete).
At present the symbiotic hypothesis for the origin of cilia seems to be limited to Margulis and a few of her associates. Margulis is, though, still strongly promoting and publishing a revised version of her hypothesis (Margulis' 1998 book Symbiotic planet: a new look at evolution has some frank autobiographical comments about her support of the symbiotic hypothesis for the origin of the cilium).
An apparent intermediate stage between spindle and cilium would be a non-swimming appendage made of microtubules with a selectable function like increasing surface area, helping the protozoan to remain suspended in water, increasing the chances of bumping into bacteria to eat, or serving as a stalk attaching the cell to a solid substrate.
Regarding the origin of the individual protein components, an interesting paper on the evolution of dyneins shows that the more complex protein family of ciliary dynein has an apparent ancestor in a simpler cytoplasmic dynein (which itself has evolved from the AAA protein family that occurs widely in all archea, bacteria and eukaryotes). Long-standing suspicions that tubulin was homologous to FtsZ (based on very weak sequence similarity and some behavioral similarities) were confirmed in 1998 by the independent resolution of the 3-dimensional structures of the two proteins.
An approach to the evolutionary origin of the bacterial flagellum is suggested by the fact that a subset of flagellar components can function as a Type III transport system.
Admittedly, all currently known nonflagellar Type III transport systems are for injecting toxin into eukaryotic cells, and are therefore presumably descended from the flagellum, which is likely older than eukaryotes. For example, the bubonic plague bacterium Yersinia pestis has an organelle assembly very similar to a complex flagellum except that it functions as a needle to inject toxins into host cells.
However, the Type III transport system still undergirds the hypothesis that the flagellum did not have to come about all at once, as a subset of components has a selectable function. That all known nonflagellar Type III transport systems are disease mechanisms is not shocking, because the Type III secretion system was only discovered in 1994 and scientific study of eubacteria is significantly biased towards disease-causing organisms. This provides another case of co-option, where a motility organelle has evolved into a "complex weapon for close combat."