Unfortunately it's not made clear in the article, but the temperature they quote is not an actual temperature, but instead a way of describing the specific intensity of the radiation. In this case the emission they're measuring is non-thermal (synchrotron emission), so the "brightness temperature" of the radiation field is not the same as the thermodynamic temperature. I'd put in a top-level comment about it too: https://news.ycombinator.com/item?id=17898224
> There's got to be some dust out there that's over the hagedorn temperature.
Interstellar dust grains are thought to be destroyed at temperatures of 1500-2000 K (depending on composition). And their absorption cross-section for absorbing radio waves is fairly small.
So far as I understand it.
My understanding of the transitions of matter between solid, liquid, and gaseous states is that it is primarily due to the amount of energy in the system. The more energy a particle has, the more likely it is to break its bonds with other particles around it and transition to another state. We tend to think of individual atoms being in some way the 'final' state once we reach some gaseous form, however it is not that great a leap to consider putting so much energy into the nucleus of an atom that its nucleus 'evaporates' into protons and neutrons (hadrons), and from there putting so much energy into those hadrons that they too evaporate into their constituent quarks. The difference in each case being that enough energy must be present to overcome each necessary nuclear force.
To be fair though, this is all very theoretical from what I've just read, and we don't truly know what happens yet.