Wow. I like the idea that Dumbledore burned Narcissa, told Lucius and the other Death Eaters and consciously relied on his good reputation to ensure no one else would believe he'd done it. That's creepy. You're right, that does take care of the "how does he have such a positive reputation, then?" objection.

I still think Fawkes would have a problem with it unless he'd tried everything else first. Fawkes is presented as quite the moral absolutist. But maybe Fawkes wasn't around - and possibly he did try lesser measures first.