You could always go for Diablo II's approach: (NOUN)(NOUN)the(ADJECTIVE). My favorite was good ol' Pukeface the Hungry.
I was acutally thinking of this very thing. I even still have the Diablo 1 strategy guide, which lists all unique monster names. I guess most of them would work for demon, devil, or some other things (maybe aberrations and undead).