I wonder what's the Death Eaters' opinion of phoenixes. If they agree that they're a force for good, seeing one of them in Dumbledore's retinue should make them ask themselves a few questions (a generic problem whenever you put a public, physical moral compass in any world, really - it becomes much harder for the villains to delude themselves into thinking they're heroes). Perhaps they think they're just creepy, winged endorphine peddlers.

Phoenixes encourage you to go out, and throw yourself full-strength against a problem, regardless of whether you can solve the problem, regardless of your chance of death.

To a slytherin, this is simply irrational. Gryffindor is brave, AKA foolhardy. Slytherin is devious AKA rational. The gryffindor method is the phoenix method: ignore the dangers that stand in the way of your goal.