In a stunning and awesome inversion, Dungeon Keeper Ami features Mukrezar. Mukrezar is, and was, a Keeper of dubious competence, given to many Zany schemes (usually involving a Ring of Power). However, since his resurrection he has shown such an assessment is significantly lacking. Apparently his resourcefulness, ability to bounce back from crushing defeat, and, most importantly, willingness to take incredible chances- and then turn them into victories even if they failed -was his greatest asset. Every appearance has only increased the estimation of his threat, despite being Plucky Comic Relief.
Discord, god of chaos and in general considered one of the best characters in My Little Pony: Friendship Is Magic, is reduced to a brainwashed monster henchman of Big Bad Titan near the end of the story and loses his reality warping abilities. To add insult to injury, he gets Killed Off for Real by Celestia.
Prince Charming, already a fairly ineffectual villain in the Shrek movies, gets decayed further to a minor protagonist in the Shrek pinball game.
Spoofed in Nebulous where K.E.N.T. mention battling "the Seaquel Devils" (a play on the Doctor Who monster the Sea Devils) - "They came back again. And again. Each time less effective than the last." Harry then reminds them of the Prequeloids - "We always knew how they did that!"
Whenever a new army in Warhammer 40,000 is introduced, they start as existential threats to the entire setting for a year or two and then decay into just another faction.
There's an obvious reason for this: profit. Make your new faction unstoppable arse-kickers who make mincemeat out of any opposition, and you've got a surefire way of getting eternal 13-year-old boys everywhere forking out on them just so that they can be the toughest tabletop warrior. Then throw out some heroic last stands for the Space Marines so that the existing factions don't get completely alienated. Wait a few years till everybody's got them, introduce a new, even more powerful, even more expensive faction. Rinse and repeat. Profit.
Necrons. When first formally introduced, they were supremely enigmatic horrors serving even more horrific beings, known for mysterious harvests of life, unknown plans, and ridiculously advanced technology. Fan perception of them quickly made them Omnicidal Maniacs to the public eye, and they began to be perceived as a race-wide Creator's Pet. The 5th Edition Codex has resulted in a serious hit to the Necrons' previously unknown and unstoppable nature in favor of shifting the focus towards the Tyranids and Chaos as the greatest threats facing humanity.
The Orks started off as a galaxy wide tide of death and destruction but degenerated into pub brawlers over time.
Zigzagged with the Orks. No one in the setting, and very few outside of it, will argue that Ork hordes aren't a serious, ongoing threat to everyone else. The problem is, Orks have kinda been stuck in the status quo area for a while, and the big videogames featuring them have them on the bottom of the Villain Pedigree.
Tyranids also started off as unstoppable, galaxy-devouring horde of alien locusts, but their impending, full-scale invasion and eating of the galaxy kept getting delayed and delayed and then the tyranids inexplicably adopted an "attack in small numbers" strategy that made them less of a threat to the setting.
Then on a smaller scale you have some of the lords of Chaos. Abbadon the Despoiler is probably the number one offender. He is supposedly the heir to Horus and carries the title of Warmaster of Chaos, as well as the favor of all four Chaos Gods. However his Black Crusades seem to end in defeat more often than not, or at best as a stalemate. One can argue on whether or not it's his fault but the community at large now looks at him as a bit of a joke, earning him the nickname Failbaddon.
Games Workshop has spent the better part of 2013 trying their hardest to dispel this notion about Abaddon, eventually resorting to retconning eleven of his thirteen Black Crusades.
In any table top rpg with a significantly steep power curve, this can happen rather quickly. Dungeons & Dragons (and Pathfinder) are the best known examples, where an enemy which is an absolute terror at one point could be a beatable boss a few levels later and a mook a few more after that. If the villain doesn't scale to the power level of each Player Character, this trope becomes almost inevitable.
Blood Boy, a big antagonist in the early stages of Survival of the Fittest version 3 had this occur in the last topic he appeared in, becoming an almost Jokeresque figure (to the point of almost directly quoting from The Dark Knight at one point). This does, however, have a fairly good reason: a different handler took over the character for that scene, one who, needless to say, had a rather different take on the character.
The Necromancer, in the Whateley Universe. Starts out as one of the top 60 supervillains on the Interpol rating scale. He's now oh-for-two against Team Kimba, who are high schoolers. Even with his team of supervillains working for him. Now one-for-two, making out like a bandit in the process, excluding one goal failing due to a Unknown Unknown.
On TWGTG, we have the Mad Scientist Dr. Insano that first appeared on The Spoony Experiment, whose early appearances depict him as a Laughably Evil, but none the less dangerous character. Later appearances, however, have him attempting no evil plans and just have him acting comedic.
The suave, chessmaster-like, psychotic Ask That Guy is slowly turning into a pathetic, needy, emotional wreck. Maybe played with because he's always been like that, he just can't seem to hide it anymore.
In his first appearance during the Nostalgia Critic's review of The Last Airbender, Shamalayan removed Critic's talent (he gets it back, even though "there wasn't much to lose"), and would have done it again in Devil if he hadn't been stopped by the actual Devil. Come After Earth, and he's become so predictable that Critic isn't even phased by him anymore.
Strong Bad, from the infamous Homestar Runner universe, used to try to do actually evil things, but he's gone under lots of Villain Decay. To quote him from the Strong Bad Email(sbemail) called "your edge"
Strong Bad: Me and the Cheat, walked past this deflated basketball and consciously decided not to re-inflate it! And we feathered Strong Sad for a HALF HOUR!
In Noob, Dark Avenger is one of the most feared player killers of the game... except a Running Gag has Sparadrap accidentally killing him. He's shown to give other characters difficulty, but it made the decay slower rather than keeping it from happening. Writing Dark Avenger out of the series due to his actor moving away relied on having that decay reach the lowest point possible.