In Pokémon, the Team Rocket trio started out being more dangerous and effective before they became... well... Team Rocket (although this may have been intentional, since the writers likely didn't know what direction to take the characters in the beginning, and chose the more comical route). In Best Wishes, they briefly went back to being more dangerous, leaving all of their comical Pokémon at the base similar to Ash leaving his team. Half the time, they didn't even bug Ash and co. anymore due to their missions.
Butch and Cassidy were originally the competent counterpart to Jessie and James, but by the time you get to their appearances in Pokemon Chronicles they've become a pair of espies.
The games have actively tried to avoid this — Team Rocket only appeared in the first two sets of the main series of games, decaying in the second one due to their leader, Giovanni, not organizing them. Since then, every main-series game and spin-off that includes criminal organizations includes entirely different ones, and each one has upped the ante for their master plans each time.
Beck from The Big O is the world champ of Villain Decay: the writers put him through almost every one of the gimmicks mentioned above. First he got a cool new weapon, then he got played as a buffoon (complete with a comically grotesque hairdo), then the hero was put into an Alternate Universe where Beck was a real threat, before he finally ended up just being an underling working for Big Bad Alex and his Psycho for Hire, Alan Gabriel.
Well, that's all true, assuming you believe he was set up to be a competent villain in the first place. In the manga, that's perfectly true, and he is a competent villain. In the anime, it's fairly obvious that he was intentionally turned into comic relief. He starts out being effective because he's actually smart enough to dial down his own ego and commence his plans intelligently. Unfortunately, his ego takes control in later episodes, and his decay is quite noticeable. Also, it's rather blatantly implied that he really isn't fit to be a villain, and that his true genius is in building robots and neural AIs (which he remains shockingly good at, as lampshaded by Gabriel, and later by Super Robot Wars Z). That said, the decay of the anime Beck is quite possibly justified.
Beck's final appearance in the manga suddenly has him become both ridiculously powerful and utterly terrifying.
The Knights of the Rounds in Code Geass R2. In their first appearance, they were shown as Britannia's elite force. Lelouch and the Black Knights were struggling when fighting only three of them (Suzaku, Gino, and Anya). But as episodes passed, they became easier and easier to incapacitate. Then, the show introduced more Knights, and after that, one of them is killed. Later, when Suzaku does a Heel-Face Turn and gets a stronger robot, he becomes able to slice down his superiors in mere seconds. However, it's probably justified due to the Lensman Arms Race being in effect, where the Super Prototypes quickly become reverse-engineered and dated in the space of a few episodes. The Knights' demise could be explained because they didn't upgrade their Knightmares enough, but the fact that Tamaki was shown to be more competent and badass, however, is not justified.
This is an ironic example, as the rest of Code Geass is quite good at avoiding Villain Decay. Any given battle is generally a toss-up, with the protagonists winning and losing a roughly equal number of battles, and almost every major villain getting in a victory or two. Cornelia is portrayed as both a highly competent tactician and fighter, the Glaston Knights are a force to be reckoned with, and Suzaku manages to win a ton of battles and lose very few. The climactic battle at the end of the first season is in fact wonby the villains of the series, while the protagonist is defeated, captured, and has his memories erased.
Subverted in Yu-Gi-Oh! with Yami Bakura. Initially he's really just a side-villain, nowhere near a main threat, and no one really spends a lot of time on him - in fact, in the first season he's defeated by the sidekick in a sideplot while Yugi is busy with the Big Bad. As it turns out, this works to his advantage, since it allows him to lurk around setting up his evil plans with no one noticing. By the time the final season rolls around, he puts all those puzzle pieces to work and becomes the season's Big Bad.
In the manga Bakura was the main villian through a volume; he was introduced in the last chapter of volume 6 and defeated in the second to last chapter in volume 7, just before the Duelist Kingdom Arc. When he showed up he was the greatest threat to Yugi and his friends ever and secretly set his plan in motion in the background. Also in the manga the psychotic level and danger of Yami Bakura was pretty clear early.
Tengen Toppa Gurren Lagann: Viral was designed for this trope. In his first appearance, he nearly hands the heroes their asses, but in every further appearance he's defeated with less effort. Despite showing up with a new upgraded mecha each time, he's eventually beaten by the humans' mass-produced mecha whose pilots don't even break a sweat. The reason for this, in-show, is because non-evolving beastmen can never match the constantly growing power of the spiral-powered humans. He gets better after his Heel-Face Turn.
Starter Villain Jadeite started off a competent threat. He had powerful minions, curb-stomped Sailor Moon during their first meeting, and actually managed to succeed in getting away with human energy in one scheme, earning Queen Beryl's compliments. But right after that last event, things began to go downhill for Jadeite. Very downhill. Once he got Hoist by His Own Petard for the last time, Queen Beryl "decommissioned" him for good. The rest of the Shittenou avoided the trope, with Nephrite and Kunzite never ceasing to be threats (though Kunzite slips when he gets his own arc, this has in-story reasons behind it), and Zoisite never being much of one to begin with so that he couldn't possibly decay (he always relied on dirty tricks in order to be dangerous.)
The Ayakashi Sisters in the manga are murderous maniacs, while in the anime they were merely misled and are granted a chance to live free in modern day Tokyo. The manga also had them capable of killing the Sailor Senshi with ease, something they struggled with in the anime. Having said that, the Akayashi sisters did display the ability to form plans in the anime, in the manga, all they did was show, beat their Senshi counterpart and then get killed by Usagi. They never seemed to pick up the fact they should AVOID fighting her when she kept killing them.
Queen Nehellenia was still evil in the anime and still a threat, but only because she was misled, and she was eventually redeemed and granted a second chance at life in Stars. In the manga, she was evil incarnate (a spawn of Chaos), responsible for the death of the Moon Kingdom and the current calamity, and was destroyed by Usagi and Mamoru.
Inverted from manga to anime with the side story villain Princess Kagua. In the manga, she's briefly beaten after a fight that lasts one panel, in the movie adaption of the side story, she nearly annihilates the Sailor Senshi and actually beats Usagi's Super Mode.
When the Menos Grande first appeared Rukia said she'd read in textbooks that only the Royal Guard can fight them. Ichigo could barely scratch it. Now that it's been confirmed that was a Gillian, the lowest level of a Menos Grande, and that any high seated shinigami can handle them. As the power levels of the main characters develop to lieutenant and captain levels, the Gillians have accordingly become regarded as mook-level threats. Even the Adjuchas levels of Menos Grande become easier to handle as the story progresses.
Aizen picks this up in a different way than the Hollows do; when he first appears, he is a bona fide Magnificent Bastard, having manipulated everyone for over a century to get his hands on the MacGuffin and pulverizing all opposition easily once it's time for him to make his move. Once the Fake Karakura arc rolls around, Aizen becomes a Smug Snake, who relies mainly on brute strength, a Healing Factor supplied by the aforementioned MacGuffin and using his own forces as cannon fodder while he sits around in the background. Once Ichigo gains enough power to completely outclass him, Aizen still relies solely on raw power instead of his story breaking illusion powers, and the intelligence he had demonstrated early in the story.
Orochimaru from Naruto suffers from some Villain Decay over time. In the Chunin Exam arc, he's too strong for any of the heroes to defeat, forcing the Third Hokage to sacrifice himself to save the village (which doesn't even kill him entirely). Then it's revealed that he lost to Itachi in the past while trying to claim his body, and in most of the battles after that, he's defeated easily or forced to retreat. This is partly because he he wasn't at full strength when he fights, but it shows that he's lost much of his original threat. This was worst when he fought against Itachi (while fighting Sasuke) in the manga, and was defeated in merely a few pages.
Also his minions from the Sound Village suffer from this, in Part 1, even the weakest of them including Filler Villain was a serious threat, and the Sound Four were so powerful that it took two of their opponents to give everything they had to kill them; in fact their leader was so strong that he would've won his fight if not for a terminal disease. When Part 2 comes around most of them (excluding those who join Hebi) are whiny wimps dependent on Kabuto.
Tarant Shank, the arguable Big Bad of Tenchi Muyo GXP, decays very fast. In his first appearance he's portrayed as an extremely dangerous and unstable villain who nearly kills Seina, Mitoto, and Kiriko, and leaves Seina traumatized from the experience. However, his next appearance has him appear with a broken arm (revealed later to be from fighting Tenchi and company off screen) and he quickly goes downhill from there; his plans are easily foiled by Seina's group, his ship is utterly destroyed, and his role as Big Bad is supplanted by Seiryo of all people. He makes a minor comeback in the final few episodes, but never quite manages to regain the same threat level he had in his original appearance.
Detective Conan: Inverted by Gin to an extreme. Gin gets progressively more evil and intelligent the longer the series goes on.
The Trinity Siblings in Mobile Suit Gundam 00 may qualify. Their first appearance sets the group up as a very skilled fighting force, with them single-handedly rescuing the other Meisters from certain capture, and obliterating most of the Union's and Human Reform League's ranks. However, following this, they're systematically defeated time after time, even, in part, by faceless Elite Mooks, until it culminates in the resident monster shooting one of them dead and effortlessly defeating the second, the third being handily saved by a timely intervention of her enemy. This can, somewhat, be justified, as they were caught off guard by both the Trial System's effects and the GN-X models, which were on par with Gundams, but the fact that they put up so little of a fight is still surprising.
The other antagonists of the second season decay pretty badly by its second half. First, A-LAWS and then Ribbons' personal squad of personality-lacking bishonen initially appear as very threatening antagonists, repeatedly pushing the Celestial Being to the brink of destruction, but then decay to Elite Mooks, with A-LAWS eventually being demoted all the way to the status of normal Mooks that die ineffectually by the dozens in the final episodes. If we count things beyond sheer combat potential, Ribbons himself decays very badly as well: after being presented as a cunning Magnificent Bastard who manipulated everyone for his own gain in the first season; in the second season he can't come up with anything better than making his puppets commit massive atrocities for no apparent purpose. This culminates with firing a Wave Motion Gun in the midst of a space battle that wipes out his own A-LAWS fleet while doing little damage to the enemy, and then using a bunch of Super Mode-powered Mobile Suits piloted by Super Soldiers as suicide weapons.
Ali Al-Saachez in Season 2, despite having become Ribbon's Dragon. It culminates in him getting shot in the face while attempting to pull an I Surrender, Suckers on Lockon II. This actually makes sense though, as most of the people he defeated in Season 1 were fighting at some sort of disadvantage, or, in Setsuna's case, were trained by Ali.
It helps that the VF-25 is far, far more advanced than the YF-21 and YF-19. Also the V-9s were under Slave control of the Battle Galaxy (that is, Grace herself). When Luca released his own V-9 escort drones via the JUDAH System, he made specific mention of them having become just as deadly as the prototype Ghost X-9.
A particularly jarring example is The Shinigami Grell Sutcliffe from Black Butler. Starts off as a supernatural serial killer with a magic chainsaw who also happens to be Jack The Ripper’s Dragon. But once they took away his chainsaw he quickly devolved into the Butt Monkey. So much so that after a handful of episodes none of the characters view Grell Sutcliffe any differently from the rest of the comic relief. Grell is still just as dangerous in the manga during the Zombie Apocalypse on the ship; it probably helps that she still has the chainsaw.
Hao from Shaman King gets hit by this hard at the very end. A thousand years old, and controls the fundamental spirit of fire (That eats souls), willing to wait a long time for his plans to succeed and very calm and calculating. There was no way for our heroes to succeed in the final showdown, even with superior numbers. So at the end he loses his cool, calm and collected demeanor and loses largely because of that.
Hao really was unbeatable and became the titular Shaman King. The anime had to pull a stock shonen ending instead of that, though, since the manga ending hadn't come out at the time, so they needed to make him lose, somehow.
Envy in the later parts of Fullmetal Alchemist. The guy who killed Hughes and generally made life miserable for every protagonist, and he's kicked Ed's ass at least once. His last two fights are against Marcoh, who uses his knowledge of philosopher's stones to decompose him (and before that he was just getting jerked around by May Chang, including getting a rock hand shoved between his ass cheeks), and Roy, who puts him through one of the worst curb stompings in manga history.
Gluttony, after a brief moment of Unstoppable Rage after learning that Roy killed Lust, is left on the brink of death after the first battle in Father's inner sanctum, forcing Father to restore him. In his next appearance in battle, Lan Fan is easily able to cut him to pieces, and Pride decides that he'd be more useful if he ate him and absorbed his sense of smell.
Buggy the Clown and his crew from One Piece spent their first appearance as a serious threat. In the manga, Buggy's first scene is him brutally killing one of his own crew members (he actually spares the guy in the anime.) But after Buggy's defeat, in all subsequent appearances he is portrayed as incompetent and having lost much of the "monster" in his status as a Monster Clown.
A lampshade is hung on this when Luffy and the group of big-name former prisoners he was with him finally escaped Impel Down. At about this point, Buggy's past on the Roger Crew was revealed, causing Emporio Ivankov to muse that Buggy is likely the 'disgrace' of the Roger Pirates.
Sir Crocodile, on the other hand, averts. He is defeated by Luffy fairly early in the story, and despite the Straw Hats having become significantly more powerful since then, he remains a very dangerous and powerful man throughout - even in spite of being removed from Alabasta, where his element, sand, was abundant. His Number Two, Daz Bones, counts as well.
Mihawk also averts this. His first appearance has him cutting ships in half with his BFS and blocking katanas with a pocket knife. The next time we see him, he has a brief fight with Luffy which Luffy quickly runs away from seeing that Mihawk is still too strong for him.
Ranma ˝ has Kuno, who, in the very earliest portions of the story, is represented as some sort of deadly, even lethal threat to Ranma...up until his first defeat, after which, he was little more than a Butt Monkey even on his best of days, with Ranma Badass Back attacks leveling him. They don't even mention Kuno as being in any way threatening even to the untrained civilians of the cast. In fact, Kuno actually managing to disrupt the status quo and gain the advantage over Ranma via some Plot Device is usually such a big deal as to be the focus of the episode.
Arguably, Giriko from Soul Eater. That is, the idea of a mad git with a chainsaw as a Weapon form does start out as a dangerous prospect, especially when he defeats the kids with no effort whatsoever meaning Justin Law had to step in (cue convenient example of the skill of a Death Scythe). Afterward, he spends too much time getting drunk and womanizing to be any kind of threat.
All those evil corporations, organizations and elite hacker groups seem pretty daunting at first in Serial Experiments Lain. The knights were particularly presented as being high-level hackers. It has you rather worried for Lain, that is until we find out (MAJOR SPOILER) that Lain has complete control of the Wired, which in its merging state with the real world, makes her God. Sayonara, Eiri! Knights: DELETED.
Kagura in InuYasha suffers this. She nearly overwhelms Inuyasha on her own in his first two fights with her, but a big contributor to that was his inability to use his Wind Scar supermove on her because she could control the air. When he gained the ability to use it whenever he wanted, he could take her easily. She was, however, still a tough enemy for the rest of the cast. What really killed her as a threat was the constant popping up of villains stronger then her.
Possibly played straight. In her first few episodes she's seen as a competent villain and legitimate threat even managing to kill a member of the Kira investigation team and finding out Kira's identity. Once she met up with Light, she began to decay fast.
Relinquishing a Death Note erases memories directly related to the Death Note, including (but not limited to) knowledge of the Notes themselves and how they work, the Shinigami, and who their users are; it does not erase unrelated memories. For example, Misa retains her knowledge of/feelings toward Light during such a time period, even though she no longer knows that he is Kira
Another one is Enishi Yukishiro who becomes less calm as the story goes on. Watsuki calls him the opposite of Makoto Shishio who ended becoming one of the most threatening villains he ever wrote.
Also, every villain defeated by Hajime Saitou. Watsuki states that Saitou ruins all of his enemies' hype.
In Higurashi, Miyo Takano went from trying to kill Rika, and become God, to trying to use the real Hinimzawa Syndrome to become "Queen of the World." Though given that it was an OVA episode...
Haruhichan parodies this in episode 3 with Achakura leaving Nagato's apartment to kill Kyon. Her result for attempting such thing? A cat attack which causes Achakura to change her mind.
Dragon Ball has this trope, and it has happened within the series on numerous occasions to the point that it's practically procedural after a villain's initial defeat.
Within the span of episodes, villains can fall from being ridiculously lethal and dire threats to being utterly outclassed in every possible way. Likely justified by the fact that the protagonists' strength grows enormously throughout the series, while most other characters stay at around the same level. A rule of thumb is that after a villain has been defeated once before, they're chopped liver. It's taken to its extreme twice: once in the Dragon Ball Z movie Fusion Reborn, and again during Super 17 arc of GT. Both times, entire scores of previously-killed villains from the original and Dragon Ball Z (and a couple from the movies!) manage to escape from Hell and are effortlessly defeated by the much more powerful cast. Even Frieza, who was offed in a single attack.
Frieza and Cell get hit the hardest by this trope in filler episodes after their sagas and the non-canon Dragon Ball GT. Each of them took a saga to be defeated, and at the time they were more threatening and powerful than the rest of the cast by a ridiculously large margin. But after their time in the story's limelight ended and new threats took their place, Frieza and Cell would become laughable at best. Frieza, on FOUR separate occasions, ate vicious curbstomp defeats, two of which were decided by a single devastating strike. Cell fares slightly better, but not by much; Pikkon one-shot him in Hell, and Goku (after being reverted to his child form) effortlessly and simultaneously made Cell and Frieza look like clowns.
The Kuwagamon that the kids meet in the first episode is a terror, hounding them for most of the episode and taking seven simultaneous attacks from their Rookie-level partners without lasting damage. The next time they encounter him, in the second arc, he menaces Tai and Agumon for a few seconds before being effortlessly destroyed by Piximon. That said Pixiemon is a well trained ultimate and the seven Rookie-level parters were newly digivolved at the time. Perhaps a better example would be the second Digimon the kids face:Shellmon. In his first appearance it takes Greymon, a champion Digimon, to take him down and even then its a struggle when Shellmon comes back three arcs later a few partner rookies took him down with little effort.
Etemon is an interesting case: he's certainly much stronger and borderline invulnerable when he returns during the Dark Masters arc as Metal-Etemon, but most of his time is spent either chasing Joe and Mimi or getting into a scrap with Puppetmon, and most of the fight with him at the end is him shrugging off attacks and boasting about his power. Though he did also kill Leomon in an attack intended for Mimi.
In SD Gundam Force, each member of the Quirky Miniboss Squad initially appears threatening when they first come on the scene. Unfortunately, in spite of some near-successes early on, they quickly become regulated to Goldfish Poop Gang, and in the second half of the series are barely able to survive. This is lampshaded by their Commander;
"But time after time you have failed. Instead of warriors, we are becoming laughingstocks!"
Omega Red gets hit by this hard in the Wolverine anime. When Omega Red first appears, Wolverine spends an episode fighting him (in a series that is only 12 episodes long) and has to finish the fight at the start of the next episode. Logan only wins because he catches a lucky break and a vital part of Omega Red's equipment malfunctions. Omega Red is repaired and made better than ever with a new arm and sent after Wolverine again, and gets killed in about ten seconds.
Pretty Cure All Stars DX 3 gives all the movie bad guys this as they're all struck down by weaker attacks than they were in their movie appearances. The worst of this was Shadow, the villain for the first Yes! Pretty Cure 5 movie, who is taken down by the fairies shining lights on his mirrors.