How to do a villain like this right

I'm hoping to have a fanfic I'm writing have a faceless unseen villain, an antagonist whom the heroes aren't fully aware of until only after the pieces start to come together, at least for a little while. But how do you do that kind of character properly?

How do you make a character so mysterious that they build up a certain amount of fear and dread, and leave you wondering "who the heck is this guy/lady?" and "What the heck are they up to?"? And while we're on the subject, how do you keep this character from suffering Villain Decay? How do you keep them menacing and intimidating throughout their entire run?

You maybe should post this in the Villain Critique Thread [1]. I just keep him like a Knight of Cerebus, make he stalking the heroes and how avoid Villain Decay. Easy, keep him like a danger of kill him in a epic way before he get a Badass Decay.

edited 15th Oct '15 4:26:42 PM by KazuyaProta

Focus on the consequences of his actions and how they affect your heroes.