Ever since Manfred von Richthofen became the terror of the skies against the Entente in World War One, every Baron automatically catches his tinge. See also The Baroness.
Comic Books
Jack Kirby's Demon had a minor villain named Baron von Evilstein.
Baron Soontir Fel of the Star Wars Expanded Universe is a borderline case. He serves the Empire, and from his last name you'd expect him to fall from grace—indeed, it's not clear for a while where his loyalties lie. He defects from the Empire, partly out of disgust about what Ysanne Isard and others have turned the Empire into, and joins the Rogues, but there are various hints that he may or may not turn again. After the comics didn't end, he vanished, captured by Isard... and, as it turns out in the Hand Of Thrawn duology, captured because Grand Admiral Thrawn wanted him. Thrawn showed him something, implied but never stated to be the oncoming Vong invasion, and Fel joined Thrawn's Empire, which wasn't part of Palpatine's Empire at all. Ultimately Fel is one of the good guys, just not the kind to wear New Republic colors.
Big Boss, the Big Bad of Metal Gear Solid. In Metal Gear Solid there is also his predecessor and mentor The Boss. With a name like that, you know you don't want to mess with her.
Warhammer 40000 has the Commisariat an organization made up of many different kinds of people from those that shouldn't be feared like Ciaphas Cain to Complete Monsters whose men would stop rebelling if he just stopped flogging them.
Count Wolf-Heinrich von Helldorf, Berlin SA leader, who also has a suitably foreboding surname.
Director
The title of choice for someone involved in a Corrupt Corporation's Mad Science department, or a secret government program. May also have a Morally Ambiguous Doctorate that they're putting to use in the program they're directing, possibly for the creation of The Virus or Super Soldiers. It's also worth noting that this kind of Director is likely the person in charge of a number of people with Morally Ambiguous Doctorates, whether they themselves have a degree or not.
Web Original
The Director of Project Freelancer, Dr. Leonard Church, is an excellent example.
Some fans call into question Doctor Doom's academic credentials since he was kicked out of State University after the accident that disfigured his face. Still, as ruler of Latveria he presumably had time to finish his thesis at Doomstadt University or have them award him an honorary one...
Doctor Cyber, Doctor Death, Doctor Destiny, Doctor Light, Doctor Moon, Doctor No-Face, Doctor Phosphorus, Doctor Psycho... DC seems to like this.
Then again ... there's been a few times when The Doctor has kindly suggested that the Monster of the Week run away. And in-universe he's made the living incarnations of Space Nazi hate-hate-hate flinch. With words. Or as the Eleventh Doctor put itwhen facing down alien of the week . "Hello, I'm the Doctor. Basically Run". They wisely did. Though this trope only applies if you are evil, otherwise The Doctor falls under Names to Trust Immediately.
In "A Good Man Goes to War," The Doctor finds out this reputation is slowly changing the meaning of his name across time from "healer" to "warrior."
This quote shows just how the name "Doctor" could be a Name to Run Away From Very Fast:
The Doctor: Imagine you were dying. Imagine you were afraid and a long way from home in terrible pain. Just when you thought it couldn't get worse, you looked up and saw the face of the Devil himself. Hello, Dalek.
While Team Fortress 2's Doctor is a boon to his team-mates, his background ("From Stuttgart, at a time when the Hippocratic Oath was downgraded to a Hippocratic suggestion") and lines ("Ze hurting is more rewarding than ze healing!") suggest he's no more kind-hearted than the others.
"Doctor Loboto" from Psychonauts likes to extract children's brains, the name an allusion to lobotomies (which would be the destruction of part of said brains, which is almost as creepy as what he does with them).
Duke Roger of Conte, so terrifyingly powerful a sorcerer no one in Tortall would dare face him except a DeterminatorAction Girl protecting her prince—and he even orchestrates his return from the dead.
Avatar The Last Airbender has The Duke, the nickname of one of the Freedom Fighters (we never learn his real name). It's ironic because The Duke is a tiny kid who was orphaned by the Fire Nation. The Ironic Nicknaming of his Gentle Giant friend Pipsqueak makes things even funnier.
Several bosses from World of Warcraft, including General Drakkisath (a dragon), General Angerforge (a dwarf) and General Rajaxx (a giant insectoid thing).
Actually, if you break his name down (from french) it is hardly frightening. It literally means flight from death. Meaning he's just a big coward. Some people should research acronyms before deciding on titles that make you look foolish.
Fleeing from death is his stated goal. He wants to use the Horcruxes to live forever.
Then again, one could also interpret that as "Flight of Death". That's a tad more frightening...
Captain, Commander and other high ranks are good too, either for villains but more so for antiheroes (or just straight up good-guy heroes). Anything lower tends to lack oomph. After all, nobody's scared of a Private. Sergeants, on the other hand...Literature
Visser Three/One from Animorphs Also Jake depending on whose side you're on.
The GreatHouses in Faction Paradox. Bonus points for their home planet simply being called the Homeworld, due to it more deserving of the name than whatever planet anyone who argued was on. They're such a humble people.
Fuhrer King Bradley from Fullmetal Alchemist. Your Mileage May Vary as to whether calling himself "Fuhrer" makes him sound even more threatening or is just a silly use of Godwin's Law. And oddly, "King" is his first name, not part of his title.
Typhus Host Of The Destroyer Plague possibly the only name to include three of the major categories out of five words and have a name that is still sinister.
The Legend Of Korra gives us Chief Bei Fong, leader of Republic City's Metalbending Police. She's the daughter of Toph from the original show, so you know she's a badass.
The swedish name of the Eurasian Bullfinch is "Domherre", litterly meaning Judgement Lord.
The title Fuehrer has been pretty much taken out of the German lexicon, except for such constructions as Reisefuehrer (meaning, roughly "travel guidebook") due to... you know who. No self-respecting German leader would dare allow the word to be applied to them these days. Any title that would have used the word prior to 1946 now uses the word Leiter in its place.
