The phrase originates from a YTMND site that parodied the Doom Episode 3 "bunny" end screen, using a picture of a cat that had been burnt to death. A YTMND user retaliated against people who voted the site up, responding when challenged that "nothing justifies 5'ing burning kittens, Not even Doom music".
The phrase "Not Even Doom Music" was abbreviated to NEDM and later became a meme on YTMND. The typical form saw a synthesised voice speaking the letters, followed by an extract from Jean Claude Ades's remix of We Interrupt this Program. References to cats and chapsticks were also common. The humor in the joke relies on the element of surprise, as references to the meme appear suddenly in unexpected situations.
The meme has since spread to other websites, where the origins are not always known.