On the other side of the fence, GDI Commandos get this reaction from the Black Hands themselves. They deserve every bit of that reputation. Nod Commandos would have a similar effect on GDI troops, except that comparatively few GDI troops encounter them.
The HP/Avengers Crossover Fan FicChild Of The Storm has the Winter Soldier. So feared that even into the modern day, the age of superheroes, wherein wizards, aliens, mutants, other similarly super-powered and genetically enhanced beings, even gods, are considered the norm, he is still, indisputably, the most dangerous man on the planet. Even Nick Fury is terrified of what he's capable of, and Loki believes he may even be the most dangerous assassin in all of the nine realms.
In the Devil May Cry and Dead or AlivecrossoverDead Or Alive 4: The Devil Factor, just about everyone in Dante's hometown is scared to death of him and won't dare mess with him or anyone else staying at Devil May Cry. Not only that, but the entire criminal underworld fears him as well. This includes The Mafia, The Mafiya, the Triads, the Colombians, and the Yakuza. It's to the point that, when he beats up an entire precinct of cops while helping Ayane and Kasumi spring their mom from DOATEC, no one even really tries to take any legal action against him.
DKA features Mukrezar, Ami's foil; where most Keepers are adressed with their full titles (like 'Keeper Morrigan' and 'Keeper Alphel') Mukrezar is always simply Mukrezar.
And later Ami becomes simply The Dark Empress.
Fate Stay Night: Ultimate Master has a rather toned down and comedic example of this with none other than Ben Tennyson, of all people (yes, thisBen Tennyson). After seeing all his forms and what each one of them can do, he raises conserns and worries among other Masters. While he gets a Servant is strong enough to match Saber, he is already more powerful than most of the others thanks to the Ultimatrix. After the appearance of Way Big, Matou Zouken goes as far as sending True Assassin to kill Ben before he becomes to much of a threat. Ironically, Ben himself has little to no interest in the Holy Gail, as he was sent by the Plumbers to investigate what the hell was going on.
Harry Potter, the Black Wizard, a.k.a. The Moristar, the Darkness Slayer. Since he's vaporized people who pushed one or other of his Berserk Button and actively hunts the Nazgul, this is hardly surprising. The Dunlending's use him as a sort of Bogeyman for the children, sort of like a Batman who's willing to kill. This makes it a bit of a shock when one Dunlending actually meets him.
In the Firefly fanfic Forward, River has become one of these to those who know about the Academy. At one point a mercenary who was briefed on her recognizes her, and he practically pisses himself at the sight
Make a Wish has Harry on holiday going under the alias of Mr Black. Over the course of his holiday he becomes the most feared wizard in the world through a combination of magical artefacts, dumb luck, and general compounding of stories about him. Wizarding criminals are terrified when they learn Mr Black is in town, and magical law enforcement tends to be torn between being glad to get his help and wanting him out of their jurisdiction as soon as possible. The less said about what happens to the Death Eaters sent after him by Voldemort, the better.
Drake from The Legend of Spyro: A New Dawn is this to the Gargoyles and Naga, who are both rather frightened at the prospect of fighting him. Turns out that despite they've got every reason to be afraid of the guy, he's actually a very nice guy. Still counts, however, in that the Gargoyles still have every right to be terrified of him.
The war god Link Sr (father of the Link we know) is feared by most of the other gods for being a murderous, disrespectful bastard who doesn't hesitate to kill someone if they offend or annoy him.
The rare physical appearance of Fate and Destiny tends to get lesser gods on edge.
The most well-known (in-universe) example would be the Originals, a two hundred thousand strong unit of mindless, violent gods - so powerful even Fate and Destiny, the two supreme beings of creation, had to settle for locking them away in an old ruined dimension.
Link himself is a literal embodiment of this trope after awakening as the God of Fear. Not only does his new status envoke fear on its own, but his first act after ascending to it? Annihilating the aforementioned Originals, and then Fate, without breaking a sweat. And then, when a several thousand strong army of lesser gods attempt to stand against him, he paralyzes them all by blasting them with fear.
Much like the Joker from DC Comics, the hideous monstrosity called Psyko terrifies even the other hardened psychopaths of Earth-2706. Psyko can emit deadly, murderous insanity, which causes the inanimate objects it affects to take on a twisted, perverted life of their own under his control, not unlike what Sleepwalker does with his own warp vision abilities. It's even worse when he affects other living creatures with them, as his victims suffer a brutal Mind Rape that forces them to continually experience their worst nightmares over and over again while he controls their bodies. His first attack on New York caused him to spread mass insanity and death across the city, and Sleepwalker only managed to subdue him after a bloodbath of a fight from which the alien hero emerged more dead than alive. For the second go-around, he mentally enslaved a horde of his fellow supervillains and turned them loose on New York City, even as he spread even more madness and suffering than he did the first time.
Starlight Over Detrot has chief Iris Jade, feared by her subordinates of the Detrot Police Department by virtue of being a heavily medicated Unicorn of not inconsiderable telekinetic power and poor temperament. To the city's less savory elements, she's the pony that managed the first real drop in crime in decades.
From Here to Eternity has Discord's younger brother, Animosity. He's SO ruthless, cruel, and powerful that even his own siblings (except Discord who is the only sibling more powerful then him) are afraid of him, even Tiff and Cacophony. And his mother is an ever bigger one! Animosity is terrified of crossing her and even Discord seems a little scared of her!
Captain Rumble from Bad Future Crusaders is universally feared by enemies and allies alike mainly due to having taken on a gryphon in a one-on-one fight and winning. It seems the only two who aren't terrified of him are Babs, who was once engaged to him, and Dinky Doo who both outranks and is friends with him.
Dinky herself, while not as much as Rumble, also has a pretty harrowing (and well earned) reputation. Fortunately, she's Affably Evil, so as long as you don't piss her off, you probably have nothing to worry about.
Naruto in one story is The Dreaded because of his killing intent when angry. It's described as leaving everyone in the area unconscious or paralyzed with fear. After Neji was subjected to it, he had to quit as a shinobi and spend the rest of his life medicated to keep from being a gibbering wreck. The Invasion never occurs simply because everyone still conscious is far more interested in going home and never angering Naruto.
In the First Try Series, anyone with a shred of common sense is afraid of Danzo. People known him since the First Shinobi War and know that it's a death sentence to be on his bad side.
The Kyuushingai in Kitsune no Ken: Fist of the Fox. In the back-story, two years prior to the start of the story, the Nine Terrors (the other name for the group) cut a bloody swath across numerous cities over exactly 365 days, and the fear that the populace felt was made worse because nobody knew what any of the Nine looked like. It was so bad that, during that time, cities that hadn't been impacted by the Nine Terrors made a point of being extremely courteous to people they didn't know, in case said strangers might turn out to be one of the Nine and cause upheaval if crossed. Furthermore, the terror they inspire was so great that Mizuki was able to take advantage of their reputation and use it to control most of Konoha Town for three months prior to Naruto's arrival there.
The entire Uzumaki Clan in The Uzumaki Massacre. So vicious that even decades after they were wiped out, Oonoki insists that he wouldn't send any less than a hundred Jonin against a single Uzumaki. And even then he wouldn't expect them to come back. Given that a force of maybe 1,500 decimated an army of over a hundred times their number down to less than 100, it's fully justified.
Yet Again with a little extra help has Ghost to the entire multiverse. Considered one of the only three "True Gods" in existence, angering him is something that no one who has even an inkling of an idea about his abilities wants to do. His most well-known and terrifying, yet awe-inspiring, title is "The God of None." It's also known that he hates that title, and calling him that in earshot is grounds for an immediate death match unless stated otherwise. In fact, it's heavily implied that Ghost is the strongest being in the universe barring the Sky-Mother herself. Thankfully, for the most part he is a perverted idiot not much unlike Naruto, so for the most part this is moot unless you piss him off.
Zeruel is this to the other Angels, the people of NERV that know of him, and the readers on the forum. So much so that when he showed up in chapter 65 and finally started trashing Tokyo-3 at the end of chapter 68, the Rebuildtrack for him was cited.
An honourable mention must also go to Iruel, partly because he's one of the few Angels to come really close to actually winning and the only one -so far- to reappear intent on a rematch, but mostly because his tactics... Well, you know how canon Eva is the Trope Namer for Mind Rape? What Iruel did to Asuka, Maya and Ichi was worse.
When the Tides Come In has Luffy from the post-canon 'verse, who by that point is the Pirate King and the World's Strongest Man. He is so terrifying to his enemies that literally no one wants to piss him off, with his haki so strong that it can easily knock out vice admirals and a temper that burns like a raging inferno. The Crocodile from his universe is so scared of him that he goes out of his way to stay out of his way and avoids Alabasta like the plague. He is completely aware that if he went anywhere Vivi or her country, Luffy would not hesitate to kill him.
Josh from Blood In The Water, specifically. In Dance Of Destiny and Let The Flames Begin, he was a Terror Hero, scaring the pants off any Plasma or Galactic Grunts he ran into. After he finally achieved Fallen Hero status, he began a reign of terror that was centered on Konar, but the aftereffects of his deeds reached the other regions and continued to inspire fear in people all across the world. He was so feared that the Konar Champion, Naomi, who was essentially the Big Good of the story, freaked out when the protagonists told her they wanted to take him on. Giovanni had a MASSIVE Oh Crap reaction when Josh appeared in his window. Even after his death, people were still terrified if they saw a Rayquaza flying around, any more than a few believed he wasn't actually dead.
Word of God also says that if Josh hadn't been killed in that final battle, he would have grown up to enslave the rest of the world with his power.
ASH of all characters, becomes this in A New Chance Series. It's an extremely unintentional example though, since Ash is still the same naive, energetic kid he always was, but due to a revised series of events he has a Latios and a Latias which he uses at the Silver Conference. To put it in perspective, Giovanni orders two of his agents, who also have a bone to pick with Ash, to infiltrate Team Aqua and Magma, but also to steer clear of Ash unless they are %100 sure they can beat him, aware of the defeats Ash has dealt Team Rocket before he got Latios and Latias. In other words, Giovanni is more apprehensive of a not-thirteen year old kid than another large criminal syndicate.
In The Lessons, Frank the Pyro is so feared by everyone in the story to the extent that the narrator at first doubts his existence due to Frank's Shrouded in Myth status. Then the narrator meets Frank...
Imperfect Metamorphosis has both Yuuka Kazami and the Shadow Youkai. The former is an impossibly ancient and powerful force of nature that even the local Reality Warper has trouble dealing with, with numerous characters voiding themselves at the very mention of her name, a reputation that she very much earns. And while the latter is known only by a few, having a habit of leaving no survivors of its rampages, as basically the Anthropomorphic Personification of death and destruction those that do know of it have no desire to face it again.
Weaver Nine: PRT propaganda would have you believe Weaver's Society has a habit of forcing innocents into its service. While it is unequivocally true the the Society has a lot of shady dealings and dubious methods, they are nothing approaching the bloodthirsty baby-eaters the PRT portrays them as. That said: Everyone knows to give them a wide berth when they show up, and it is well deserved. The Society is constantly besieged by bounty hunters, rival villain organizations, the Yangban, Cauldron and their puppets in the PRT and Protectorate. They survive because they are harder, stronger, and both more ruthless and more vicious than their opposition and willing to use every asset at their disposal. Up to, and including, the lobotomized bodies of their attackers.