1) Myxozoans have been known for quite some time (the taxonomic Class was erected in the 1970s), and it has been known since they were first discovered that they have no mitochondria. Therefore, it has been known since soon after they were first discovered that they are obligate anaerobes.
This would make them unique among metazoans (i.e., animals). However, Myxozoans are rather odd metazoans in the first place (in fact, for a long time they were considered protozoans). This is probably due to the the fact that they are obligate parasites (parasites are often very highly derived, and sometimes almost unrecognizable as members of their higher taxonomic groups). For instance, Myxozoans, although Cnidarians, were note recognized as such until about two decades ago.
2) Cellular respiration and "breathing" are two different things. Cellular respiration is when glucose is metabolized via oxidative reactions. "Breathing" is the mechanical movement of air in and out of the body. The term can also be used to refer to the movement of oxygenated water over specialized gills. While both are called "respiration" they are NOT the same thing. There are many metazoans that do not breath (or even have specialized gills), and get their oxygen via simple diffusion over the body wall. In fact, this is true for most Cnidarians -- the Phylum to which Myxozoans belong.
3) The cool finding here is that there are no remnants of mitochondrial genes in the Myxozoan genome. Since the phylogenetic of the Myxozoa indicates that they are derived from Cnidarians, and all other Cnidarians are aerobic, this is a bit puzzling -- normally one would expect there to be some remnants to disused genes, even if their initial deactivation was in the distant past.