Vergil in Devil May Cry 3 goes from handing Dante his ass during their first encounter, to fighting him to a stand-still in their second, and finally losing to him in their third. However, it's not so much that Vergil forgot to level grind, since he actually gets progressively stronger just like Dante, gaining new weapons (Beowulf, Force Edge) and attacks, but Dante's just gaining much faster than he is.
In The Legend of Zelda I, a completely unaltered version of the level one boss returns guarding level seven. With the best sword in the game — which is obtainable by that point — he's a One-Hit KO.
This happens a lot in Zelda games, though often the boss will bring some of his friends the second time to offset his relative weakness. It still gets played straight sometimes, such as the giant scorpion boss in The Legend of Zelda: Skyward Sword, which reappears later... after your sword has been upgraded to do double damage, making the boss much easier to kill.
The SA-X in Metroid: Fusion. Justified by the fact that it possesses the thing that can completely screw you (the Ice Beam) if you ever cross paths. Only after you get the Varia Suit (to block the freezing) and the Plasma Beam (to pierce the armor and hit the softer X core) does it lose its edge against you and Samus become able to beat it.
Though this is actually an Up to Eleven version of the trope, as the SA-X is downgraded to a boss battle (and a tough one at that) from being literally unbeatable.
The first round of bosses in Terraria are a real challenge, particularly the Wall of Flesh. Once you reach hard mode and acquire its dramatically more powerful gear, they'll come off like pushovers. For comparison, the final normal boss has 8000 hit points. The most fragile hard mode boss has 30000.
In Mega Man X6, the first battle you have with High Max is an automatic loss. No matter what you do, he cannot be damaged. Of course, as you go along the game and subsequently encounter him again, he will be damageable by a few weapons you acquire from the boss Mavericks.
Mega Man ZX: Aeolus and Siarnaq intercept Biomatch Model A at the Tower of Verdure with the intent to claim Model W; even though both of them are together, Aeolus decides to let you off the hook, confident that he can "end you at any time". How wrong he is when you fight him proper.
The last time you see them before the Final Boss, however, all four Guardian Biomatches show up in the same room with singular intent to shut you down. It would have gotten messy had Biomatch Model X not shown up to provide a diversion for you.
Siarnaq: Tactical advantage four to one. Commence complete destruction of target.
Massively Multiplayer Online Role Playing Game
In City of Heroes, Frostfire, the first Elite Boss most heroes will encounter, later appears in several tip missions, although by that point he's become a regular boss (which means depending on your difficulty settings, he may even spawn another tier lower, as a lieutenant). A hero morality mission also features Nocturne, an archvillain from the Faultline arcs, as a regular boss.
Final Fantasy XI: Averted in many fights. Instead of having the fights based off of your level, your level is restricted in several missions as well as optional "BCNM" fights. Recently, most of the mission fights had this restriction removed, due to the lack of players willing to help as well as the difficulty level.
RuneScape: In "Legends' Quest", the player must fight the same demon three times. Since the player is not required to progress in a started quest, the player could choose to level grind between the various encounters with the demon in the quest. The result could be a final boss that is much easier to defeat than the first two bosses.
Subverted in "While Guthix Sleeps" and "Ritual of the Mahjarrat" quests. Despite being only Level 14 in the Temple of Ikov quest, Lucien becomes immensely powerful and obtains two god-weapons.
World of Warcraft bosses tend to this, such that players will occasionally revisit particularly frustrating dungeons 20 or 30 levels later for the pleasure of curb stomping the boss that gave them so much trouble the time before, sometimes even single-handedly. Aversions to this are Heroic dungeons, where two versions exist, one for top level characters. Also the sorcerer Arugal, who appears as the boss of a 20th level dungeon, then is resurrected as a 70th level elite. Arugal's former residence Shadowfang Keep, while he's no longer present, also gets a heroic mode. This leads to a 65 level difference between the normal and Heroic mode. The similarly-leveled Dead Mines also get an 85th level version. Seeing as it's supposed to be a direct threat to Stormwind itself, this is appropriate.
Averted by bosses that appear again in a higher level dungeon, especially if they're moving from 5-man dungeon to raid. Anu'barak, Thorim, and all three Blood Princes multiply their hit points several times over by the time they show up as bosses.
The Naxxramas bosses go from Level 60 to Level 80 in Wrath of the Lich King (an expansion pack that focuses on the battle against the Scourge, which includes the residents of the dungeon), but in the 10-man versions, some of them have fewer hit points than their original 40-man counterparts. Ragnaros has recently returned at Level 85.
Kael'thas actually devolved a few levels, between his appearance in the endgame raid Tempest Keep and his coda as the end boss of five-man Magister's Terrance. Given that he was severely injured in Tempest Keep, and still has a giant chunk of crystal embedded in his chest, it's understandable.
Tetris Attack and Pokemon Puzzle League have a single-player campaign which consists of a series of levels with gradually-increasing speed. Halfway through both games, there's a special level where you essentially fight the final boss with a speed of about 45 (from the previous level's 20.) The thing is, if you keep playing through the game, the final level/boss has the same speed of 45, while the previous level's speed this time is 40. (Incidentally, you can beat the boss at the halfway point just as easily as at the end of the game - doing so just gives you a cutscene and puts you at the second half instead of ending the game.)
Barkley, Shut Up and Jam: Gaiden has this with Michael Jordan and Vinceborg; they both seem to be a little more powerful the second time you fight them, but your strength and numbers make both rematches fairly anti-climactic (especially Jordan). Plus, you fought both at the same time the first time, and separately the second.
In Baten Kaitos Origins, you fight Giacomo three times. In the third match, he's no stronger than the second match (only gaining buffing abilities), while you've probably gotten at least two or three levels and new magnus. Extremely satisfying, especially since the first fight is an infuriating Early Bird Boss.
Barubary in Breath of Fire inverts this, but then again, the Final Boss Preview (or rather The Dragon preview) IS him just picking on a little kid in the prologue. Grown up and come back with a real sword, you stand a much better chance, though it's still possible to die.
For all practical purposes, Spekkio in Chrono Trigger pulls the level capped variant of this. Spekkio "levels up" with your strongest character, but once you reach level 50, he won't level up again until level 99, which most players only reach for the sole purpose of fighting this boss in his ultimate form. At level 65, you have him completely outclassed.
And before level 50, he only actually transforms at every 10th level. If you take advantage of this and fight him one level before he upgrades, he poses little threat.
This also occurs in New Game+, where after running through the game a couple of times, Lavos can be defeated at the very beginning of the game with just Crono and Marle - or even Crono himself.
Magus is fought at the grand finale of the 600 AD subplot, and it's a grueling, drawn-out slugfest that takes three party members punching through an elaborate magic barrier. Later on, one of your party members can choose to duel him one-on-one, and his stats are pretty much exactly the same.
The most noticeable instance is the Boss Rush at the end of the game. Lavos mimics various bosses from throughout the game, without boosting any of their stats. The first several go down in a single hit.
With the minor twist that they are heroes that just refuses to listen to your (Cthulhu's) explanation, a would-have-been Goldfish Poop Gang (the developers forgot about them) is one of your first major fights in Cthulhu Saves the World and in the enhanced PC release is also one of the last non-random fights — only that time it's not major at all, since they are exactly as strong as the first time.
The Avatar of Khaine in Dawn of War 2 is a nightmarishly difficult enemy, with abilities that will one-shot most of your squads, three hundred thousand health, and a crazy amount of support requiring Terminator armor, plasma cannons, and thirty to forty minutes of alternately beating on it and running away to defeat, combined with several orbital bombardments. When you run up against another Avatar in the Chaos Rising expansion, however, it's still got three hundred thousand health and the same abilities, despite the fact that your squads are six or eight levels higher, and can be defeated with conventional weapons. In fact, the only reason the Avatar in Chaos Rising isn't a Curb-Stomp Battle is that you don't have Terminator armor or Orbital Bombardment at that point in the game.
Happens a few ways in Dragon Age: Origins. While enemies level up in scale with you, many of them don't gain any new abilities, while the party does. Those new abilities are often able to even out or overcome the advantages that some of the tougher early-game enemies have.
The first ogre you meet is a Wake-Up Call Boss that will kill you if you aren't prepared for it. By the endgame, three or four of them together don't pose nearly the threat that the first one did.
Also, the Revenant. The first one is, most likely, going to be the toughest one of all. The thing is powerful, tough to kill, and likes to pull ranged attackers to it. Each subsequent one is slightly weaker due to your Level Grind. While none of them are truly weak, the last one you're likely to encounter will hardly give you any trouble.
As far as individual characters go, Ser Cauthrien was an incredibly difficult encounter that you were meant to lose so that you could ultimately be captured. Fighting her before the Landsmeet, she's a medium difficulty boss that goes down with a minimum of fuss. Note that these can happen pretty close to each other, and in fact she's made physically weaker (and backed up by fewer mooks) in the second encounter.
Dragon Quest IX has a not-so-Quirky Miniboss Squad in the Triumgorate, and each member of the trio gets their own separate boss fight with plenty of hype leading up to it (except Goresby-Purrvis). And then, in the Realm of the Mighty, you have to fight them again...while they've apparently gained exactly zero levels in the meantime. Vaguely justified in that their pre-battle dialogue implies that they were very recently resurrected, but then again, given the power of the Big Bad behind them, you'd think they'd be made a lot stronger.
Given who the Big Bad is, and that he's gone quite insane, this is Justified.
Happens as a result of a "feature" that is almost certainly a bug in The Elder Scrolls V: Skyrim. Unique NPCs don't "level up" with the player, being stuck at the level they were first spawned (unlike ''Oblivion'' or Fallout 3, where key NPCs would automatically level up to match the player). Two key NPCs, Ulfric Stormcloak and General Tullius, are spawned at the very beginning of the game. As a result, when you finally face one or the other of them at the end of Civil War questline, they're stuck at their minimum level and are easily dispatched by a mid-to-high level player.
(After several months, they finally patched this during the first DLC release. The engine now re-calculates the NPC's level each time they get loaded in a new cell.)
Final Fantasy VI: Kefka is an inversion of this trope. At the start of the game, he's a joke who bails from even the most basic blows Sabin can dish out. He does scale up in power very quickly due to his manipulation of the Espers the Empire controls to the point where he not only kills off the Anti-Villain and fubars the peace conference in Thamasa, but also overthrows his own boss, fubars the whole world, and rules over it like an Evil Overlord.
Played straight with Ultros. The first time you meet him, he can one hit any of your party members. Later, most of your party members will be able to one hit him.
Final Fantasy VII: The Midgar Zolom is a Total Party Killer when you first run into it. Fleeing from the battle or avoiding it altogether is the only way to survive. Come back on Disc Two or Three and well ... see the top of this page. (If you come back after visiting the North Pole, you'll have a hard time acquiring the Zolom's "Beta" Enemy Skill on your latest materia, because by this point, your Cherry Tapping will One-Hit Kill the Zolom.)
In Final Fantasy VIII, while enemies will level up with you, all the mandatory bosses have a level ceiling, that gradually increases throughout the game to 50. The optional bosses can still go all the way to level 100, though.
Final Fantasy XIII has Barthandelus' second form, which is fought at the end of Chapter 11 and falls squarely under That One Boss. He returns as the first form of the final boss fight, where all but one of his attacks are laughably weak and he loses the ability to inflict status ailments. (Granted, the 'one' falls squarely under That One Attack, but it's still easy to recover from).
Saturos and Menardi in Golden Sun run into this pretty hard, since Isaac and company go from kids with magical powers to powerful spellcasters who happen to be kids. They're completely unbeatable in their first appearance, only beatable because of outside factors (and the fact that only one of them is there) in their second and then entirely beatable (although with difficulty) even after fusing into a two-headed dragon in their third.
The entire concept of level grinding is foreign to anyone besides the main party. Saturos and Menardi stay at roughly the same level throughout the series (getting weakened or strengthened through outside forces, never their own), Felix and Jenna are just as wimpy (level-wise) at the start of The Lost Age as they are (well, Felix is implied to be a poor fighter, Jenna just has a low level cap when she's playable) at the beginning of Golden Sun even though they've been traveling with Saturos and Menardi, Alex has trouble wrapping his head around the concept that Isaac & co. could beat Saturos and Menardi, and Isaac & co., despite spending months at sea, obviously fighting random battles, don't gain a single Experience Point between the end of Golden Sun and when they join you in The Lost Age.
Subverted with Alex. He starts out as the series' most powerful character, then grinds hugely at the end of The Lost Age, and appears to have ground even more with the coming of Golden Sun: Dark Dawn, effortlessly OHKOing a main character.
Darth Bandon from Knights of the Old Republic is such a powerful figure in his first appearance, in the tutorial level, that you aren't even given a chance to fight him. He appears later on as a not-particularly-tough boss. Calo Nord as well, especially if you count his first appearance, effortlessly stomping three Rodians. And your party, if you fight him in the cantina.
The second game has the Twin Suns on Nar Shadda, who you have to fight with just Atton in the cantina first, and then the second time you get your main character and any two party members to turn it into more of a Curb-Stomp Battle.
The True Final Boss of Live A Live has the main villain pitting the individual characters in rematches against the final bosses from their respective chapters. However, if you have rotated the group throughout the final chapter to level all of them up, as well as getting the ultimate weapon upgrades for each character, this time, the bosses aren't nearly as powerful.
Morag in Magi-Nation is fought in an Unwinnable Boss Battle. By the time you fight him for real, he's...well, he still puts up a fight, but isn't nearly as powerful as the first time he almost kills Tony Jones.
The Collector ship effortlessly pwns the Normandy in the opening scene of Mass Effect 2. Make the right investments, talk to the right people, and do the right research through the game and that same ship gets pretty effortlessly obliterated by the new Normandy.
In Mega Man Battle Network 3, the first time you fight Bass, he is an unwinnable boss fight. The second time you fight him right before the final boss, he has low HP, and no really damaging attacks. Then you face him as a Bonus Boss, and get utterly destroyed by him.
Parodied in Mother 3, where the mole cricket you fought in the very first battle challenges you to a rematch... in the second to last chapter of the game. Interestingly enough, according to him, he has trained the whole game for that match; but he's, well, a bug. A normal-sized bug. The only noticeable boost he shows is in speed, so he can show you how much of a pushover he is before going down.
In Paper Mario: The Thousand-Year Door, Doopliss has the same health and attack power when you fight him alongside the other Shadow Sirens in Chapter 8 that he does when you face him alone at the end of Chapter 4 (both the fake end and the real end). Meanwhile, Beldam and Marilyn have become stronger since the last time you fought them, as has Bowser.
Rawk Hawk never grows any stronger no matter when or how many times you fight him. Especially jarring, since he explicitly says he's been training like crazy, and even sends Mario an e-mail asking for a rematch.
Strega from Persona 3 aren't a huge threat the first time you fight them, but they don't seem to have become stronger at all when you fight them again, months later.
Strega actually do go up somewhere between 10-20 levels by the final fight against them, it's just that you've most likely gone up 30 to 40 levels in that time, especially if you shoot for the level cap. Plus the first fight against them features both Jin and Takaya (it's still pretty easy), whereas all the subsequent fights are against only one at a time. They're mostly there as a speedbump to demonstrate that despite the doom-and-gloom they've been helping spread over the past couple months, The Power of Friendship and hope can triumph over their nihilism.
This is the intrinsic problem with Gym Leaders in Pokémon. The player has the ability to level grind after being beaten once, then come back and stomp the Leaders flat the next time around; the Leader has to stand there and take it.
Giovanni in Pokémon Red and Blue seems to be an example of this trope. The first time you fight him, his Kangaskhan will be ripping through your party left and right. It's somewhat easier the second time you fight him at Silph Co, as your Pokemon will have started evolving and learning better moves, whereas before Kangaskhan was using moves that were really strong for that point of the game. When you fight Giovanni in Viridian Gym, it is painfully easy. All of Giovanni's Pokemon are of the Ground type, with many being Rock types as well. That is the very first type you learned how to exploit back in Brock's Gym, and to make matters worse, you just got done facing a Fire Gym, so you're almost certain to have a decent Water type on you who can rip through Giovanni's team.
This becomes especially problematic in Pokémon Platinum; after the Elite Four, the player can explore the island where Battle Tower is — north of the tower is a hangout for Gym Leaders and other elite trainers. At first, a player who doesn't level grind will find the rematches challenging, but once their team starts growing past the Gym Leaders, said leaders will no longer be a challenge — they're stuck in the Level 60's.
The Rival stands outside this building, where you can fight him on the weekends. His levels are also a little tough at first, but you quickly surpass him. There is a way to make him increase his levels, but you have to beat the Elite Four twenty times.
Averted in Generation 5, as the Elite 4 grow more powerful the more times you complete it.
However, Pokémon Black 2 and White 2 has the Pokemon Breeders who challenge you every time you enter their area. Not so bad the first time, but after you finish the game, they still challenge you, even though they're at level 20 or whatever and you're nearing level 100. Cue Curb-Stomp Battle.
There's also the hilarious Curb-Stomp Battle when you fight Baltor for the second time. The first time around, his pirate ship is a legitimate challenge. The second time, he's got exactly the same ship. You've got the Delphinus and its Moon Stone Cannon.
Lampshaded in Suikoden Tierkreis. After beating the crap out of Conon (who had been half of a Hopeless Boss Fight several times by this point), the hero wonders why he's so much weaker all of a sudden. Liu tells him he isn't, he just hasn't been getting any stronger, while they have.
The Four Horsemen in Summoner. You can run across them early in the game in random encounters, but you can't kill them. All you can do is try to survive and get their hitpoints down until they leave for some reason, and that's hella hard. When you reach them in the main storyline, much later, then you can kill them.
In Tales of Symphonia, you fight the Big Bad Yggdrasill four times. The first time, he obliterates you in seconds. The second time you fight him, he has the same stats and you can hold your own against him until the battle is interrupted. The third time, he's actually weaker and doesn't spam Outburst. Then again, you're not supposed to win against him the first two times... He does get stronger when facing you the last time, as the Final Boss.
Early in The World Ends with You, Uzuki "can erase you in a second." Once you've reached level 30, she's much less intimidating. The same goes for Kitaniji, who's amazed at how much power you've gained.
Princess Maker has characters who are ostensibly supposed to be 'rivals' to your progeny. However, they remain at exactly the same level while your little princess grows strong enough to defeat the God of War.
Turn Based Strategy
Often in Sid Meier's Civilization series of games, the human player will find that although the AI civs have advanced technologically at similar (or even greater) pace than the player did, they've failed to upgrade or replace a lot of obsolete units, even defensive ones (sometimes a human player may forget to as well). So once a player polishes off a couple of updated defensive units in an enemy city (or advances past better-defended outer cities), they find themselves fighting... pikemen or spearmen with tanks. Seemed to happen more in earlier editions of the game, by III or IV the AI was a bit better at upgrading. (And if in Civ II they had the Leonardo's Workshop wonder, such upgrades would be automatic.)
Very, very common in many of Nippon Ichi's games such as the Disgaea series, due to the insanely high levels you can reach - the plotline fights are scaled on the assumption that you'll mostly only gain levels from plotline fights, and not go gallivanting off to the Dark World or Cave of Ordeals or Land of Carnage. Even fights where you're supposed to be curbstomped by the overwhelmingly powerful boss (Beauty Queen Etna, anyone?) can be won through higher levels and good equipment, although that sometimes lead to a Nonstandard Game Over due to plot derailment. (Defeated Feinne too early? Here comes Asagi to ruin everything and forcing you to start all over again.)
Downplayed in Phantom Brave, however. Your steal resist is based on your level and class title. If the boss begins the battle unarmed and all you've done is powergrind your WEAPON and not your character...he'll just steal it and slap you with it for a One-Hit KO without batting an eye. Due to their high steal rate Fun Guys and Bottlemails eventually become among the worst enemies for high-level characters to face down with weapons. So essentially they didn't need to level because you were nice enough to provide them with an alternative means to kill you.
The easiest way to grind experience and Mana is to create high-level dungeons and attach a weak title to it so that the enemies inside have reduced stats...but they will still retain their high level and steal rate, meaning you're in for a beating if you can't kill all before they get a turn.
A handwave as well: when you beat Bonus Boss Laharl for the first time, he rounds up his minions telling them to upgrade his weapons in the Item World.
Final Fantasy Tactics: Some battles have enemies that level. Monsters do, Humans don't. It's not uncommon for max-level characters to just go by and slaughter them, or for Zalrea to summon high-level monsters while the undead are significantly weaker. Not to mention; in Tactics, it's kind of a bad idea to level your characters up too much in the first chapter, because you have access to all these cool classes, but none of the stores sell equipment they can use, making you essentially gain a bunch of Empty Levels.
Story battles do no scale with your own level but random battles do. Whether the enemies are monsters or humans does not matter. Due to this, you can gain access to the most powerful non-rare equipments as early as chapter 2, when human random battles become possible.
A perfect example of this is Valter, who promptly kicks Seth's ass during the Prologue (it was a cutscene but the stats were there). Come Scorched Sand and he reappears, not having changed a bit since then, and your party has had 'plenty' of opportunity to level grind in the Tower of Valni.
A strange subversion in Awakening: the boss of the Premonition appears early on in the actual story weaker than in the first battle, but that's justified since the Premonition is a dream of the future. Come Chapter 23, and the boss appears exactly the same as it did in the Premonition, meaning you should be able to easily curbstomp it...until you do and it turns out to have been hiding its true power, resulting in a rematch where the boss has stats actually befitting a boss this late in the game.
Tactics Ogre as well as Knight of Lodis have this show up. To elaborate, the games use a system in which the enemies will be around your characters' levels (Specifically, the leader's level). However, after a certain point in time, the enemies in story battles stop leveling up, meaning you can go in and slaughter the final enemies at level 50, when they only cap out around the 30s.
Non-video game examples:
Anime and Manga
Bleach has an aversion with Grand Fisher, who is barely defeated by Ichigo early in the series. He comes back, explicitly points out how he did remember to level grind, only to be Killed Off for Real by Isshin Kurosaki in a Single-Stroke Battle.
Gillians could also play a straight example. The first one that shows up takes Ichigo and Uryu working together just to wound it bad enough that it runs away. Now the Villain Pedigree has shot up so many times that when Gillians appear, they're Giant Mooks and are only considered a threat if they're in large numbers.
Every monster from Claymore suffer from this. Justified by the fact that while the heroic Half-Human Hybrid ability increase with time and training, the full monster are at the top of their power and thus unable to improve. One notable example is when monster of the same power level are meet before and after a long Level Grind sequence: the first was narrowly defeated after a long battle which require sacrifice, technique, and luck, while the second one was defeated very easily.
Most of the Big Bads in Digimon Adventure require someone getting a new form that can beat them. The Dark Masters, however, didn't. In their first appearence, they take turns beating the stuffing out of the Digidestineds' Digimon, Piedmon defeating both their Megas with no effort at all. Well the Digidestineds' Digimon don't get new forms, so they get more experienced and stronger with the ones that do have. They beat MetalSeadramon and Machinedramon of them by wisely using WarGreymon's Dramon Destroyers, which are super effective on Dramon type Digimon. Puppetmon is downed in one hit from MetalGarurumon but Piedmon gets it the worst. Even though MagnaAngemon played a big role in his defeat, the same two Mega Digimon he effortlessly beat down before back him into a corner and force him to pull out his most underhanded trick. Even without them, the Ultimates in the Digidestineds' arsanal still manage to put up a good fight against him and once his trick is no longer of use, he gets his butt kicked. He saved himself for last but didn't bother getting stronger, so the Digidestined were able to catch up.
In Digimon Frontier, the Royal Knights got hit by this hard. When they first fight EmperorGreymon and PlasmaGarrurumon, they beat them in a Curb-Stomp Battle. Subsequent battles can best be described as the kids losing less badly. In "To Make the World Go Away", they are evenly matched against the Royal Knights and Lucemon needs to intervene to defeat them. In the very next episode, they curb-stomp the Royal Knights. Each fight made EmperorGreymon and PlasmaGarrurumon more skilled, but the Royal Knights didn't learn anything new.
The Otherworld Tournament Saga in Dragon Ball Z. Almost every foe Goku had faced caused a riot in Hell. Goku and Picco...er, Pikkon go and beat their asses (Freeza and Cell are actually a threat at this point, but much less than they were when they were Big Bads).
In Dragon Ball, Tao Pai Pai, who went from possibly the strongest human fighter on Earth and the first opponent to hand Goku a solid defeat early in the original Dragon Ball to a below-average enemy only able to defeat the weakest of the supporting cast before being beaten senseless by a mid-level supporting cast member in the Tournament Arc at the end of the series. When he appears again in Dragon Ball Z (albeit only in the anime), Goku is so out of Tao's league that he's basically a joke villain who spends the episode engaged in whacky hijinks trying (hilariously unsuccessfully) to outsmart Goku. When Tao realises Gohan is Goku's son (after using his signature move which didn't harm Gohan), he quickly flees.
Pilaf. This little guy and his halfwit minions first appeared when the series was more gag-oriented. They would appear again when the series beginning to focus on action more, trying to steal Dragon Balls from Goku, right after he had become strong enough to defeat an army of terrorists single-handedly. To say the battle was one-sided would be a bit of an understatement. In fact, they themselves invoke Cerebus Syndrome by releasing Demon King Piccolo, who was the incarnation of Kami's cast-off evil.
Kwi, Dodoria and Zarbon, all being part of Freeza's army and mostly taking it easy as they conquered planets. All three were known to either have the same battle power as Vegeta or a far higher reading. That is, until Vegeta's battle on Earth. One by one, Vegeta manages to pick off Freeza's men, especially noting that his powers have gotten stronger as he was in more extreme fights than Freeza's men have been, relaxing around him. The better example being Zarbon, as he defeats Vegeta with ease once he transforms during their first fight and nearly kills him. After their second fight, Vegeta reminds Zarbon that a Saiyan's battle power increases every time they recover from a near-death situation, ultimately resulting in him killing him off with relative ease.
A borderline example when Freeza comes to Earth, only to be summarily sliced in half on arrival by Trunks (he did gain in power due to cybernetic implants, it just wasn't enough). Played straight in one of the movies where the forces of Hell break out, which includes a rightfully pissed off Freeza. Gohan kills him with one punch.
Taking into account all of Z, GT, and the movies, Frieza returns and gets curbstomped pretty much immediately no less than five times; once with King Cold and four times after his death. After being killed by Trunks, he terrorizes Hell and gets wrecked by Pikkon in a couple hits. He gets back to the living world in the movies Fusion Reborn and Plan to Eradicate the Super Saiyans, but gets beaten up by the end of each movie. Perhaps his most embarrassing reappearance was in GT, where he gets beaten by an ice machine.
Subverted with Cell. When he first appears, Cell drains humans of their life force by sucking every last bit of their body through his stinger. This allows him to receive nourishment and to increase his battle power. He starts off being slightly weaker than Piccolo after he fused with Kami and Android 17. After absorbing thousands of humans, he becomes more powerful than both Piccolo's and 17's combined attacks and beats them senseless. He later achieves his main goal of absorbing the two androids and makes a massive jump each time in power. He also possesses the Saiyan's power to recover from near-death and come back stronger, though he is permanently defeated shortly after displaying this ability.
...And this happens AGAIN in GT, and while far more villains are actually seen being killed than in Fusion Reborn, all of them are killed with no effort whatsoever.
Justified for the dead villians. In the series it's explained that only people going to heaven can retain their bodies to become stronger. One exception was Vegeta during the Majin Buu arc.
Kagura from InuYasha nearly kills the eponymous character in her first two fights, but in the 3rd he's got a new ability that gets around her keeping him from using his best attacks, so he stomps her. Just about every other recurring villain in the series, however, also gets stronger as the series goes on, depending on whether they survive long enough for Inuyasha to get a new upgrade for the Tessiaga.
Many of the opponents Kenichi faces off in Kenichi: The Mightiest Disciple often suffer from this. They are usually really good at their martial arts style, and will probably give Kenichi a beating the first time around. However, due to his intense Training from Hell he receives from various martial arts masters, he becomes a Combat Pragmatist and gets pretty good at defending himself. In one fight, when fighting against Takeda the Puncher, Kenichi focuses on his legs, which is a boxer's weakness, and helps him to get the upper hand in the fight. Since he's not a villain however, Kenichi will usually win them over with a speech or by giving them help (in Takeda's case, taking him to Master Akisame, and having him fix his crippled left arm, which allowed Takeda to take up boxing again), and many of them help him in later fights.
Fate's minions in Mahou Sensei Negima! fall under this pretty badly; in their first appearance, they're perfectly capable of taking on the noncombatants of Ala Alba despite being outnumbered. Unfortunately, the next time Ala Alba shows up, most of the girls have either done additional training or pactio'd and obtained powerful artifacts, leading to an ignominious defeat for the minions, who haven't really improved since last time. Fate himself, while still a legit threat, reveals that the concept of training is quite alien to him. It shows, too. Every fight he has with Negi has Negi doing slightly better than beforehand until the final fight where Negi is doing a lot better and obviously has the advantage and WON.
Most recurring villains in Naruto play this straight, stomping the cast in their first battle, but losing as the heroes become stronger. Spectacularly averted though, by Kabuto, Orochimaru's Bastard Understudy. When he first appears he's a Jonin level threat, who could probably give Kakashi a decent fight. But after incorporating some of Orochimaru's remains into himself, and mastering Edo Tensei he's become a Kage-level threat with a small army of undead heroes and villains all prepared to Boss Rush the main cast. Between these moves, his ability to genetically engineer monsters like Manda II, and whatever else he's got up his reptilian sleeves he's gone from Combat Medic, to part of a Big Bad Duumvirate alongside Tobi, the series' Big Bad. And his latest revealed ability, Snake Sage Mode even made Itachi go Oh Crap.
If it wasn't for Sasuke, Itachi wouldn't have been even able to useIzanami on Kabuto. He had literally defeated Itachi twice there, first by impaling him from all sides with Mushi Tensei, then bisecting him after revealing he had mastered the powers of the Sound Four. Talk about Near Villain Victory.
The Pacifistas in One Piece. Nigh-indestructible cyborgs that shoot lasers. The Strawhats were lucky to take down one of them. Cue the Timeskip. Luffy one-shots one, and Zoro & Sanji double-team another. Though one hit from either of them would have been enough.
Though Sentomarou hint there are stronger models of the Pacifistas now.
There's also Buggy the Clown. He's the first opponent Luffy actually had to work against (i.e. fight lasted more than one chapter), and after an attempt at revenge in Logue Town, pretty much disappeared from sight. When he and Luffy meet again in Impel Down, the only thing that's different is the fact that his town-destroying Buggy (Cannon)Balls are now marble-sized.
When Ryoga finally manages to find his way back to Tokyo in Ranma ˝, he immediately challenges Ranma again. Who has spent the whole time having to fight several extremely strong opponents, most prominently Cologne. So the challenge turns into a Curb-Stomp Battle. Ryoga turns out to be Genre Savvy enough to just ask Cologne to help him. And since Ryoga wants to marry Akane and Cologne wants to prevent Ranma from marrying Akane so he can marry Shampoo instead, she's quite willing to help rather literally help him grind.
Subverted in Rosario + Vampire with Kuyou in his reappearence in the Fairy Tail invasion arc where he is shown to definitly have remembered to Level Grind. Double subverted in that Tsukune had levelgrinded even more.
Viral from Tengen Toppa Gurren Lagann demonstrates the tendency of the trope to cross over with Ineffectual Sympathetic Villain. As dangerous as he is in his first appearance, he never goes down in personal capability (and improves with each appearance, in fact), but the heroes go up every time faster than he does, thus making poor Viral an increasingly weaker threat. Until his Heel-Face Turn, anyway. It didn't help that all of his improvements went towards his mecha's swordsman abilities (instead of his ranged attacks), which were completely useless in their first battle.
Averted in Toriko. Since the major villains also have Gourmet Cells, they are able to become more powerful just like the heroes. Tommyrod in particular went from keeping a level 81 insect hybrid inside himself as his ultimate trumpcard to becoming strong enough that one of his arms has a capture level of over two hundred. Starjun was already stronger than Toriko for most of the series, and after Toriko took a few hundred levels in badass Starjun still defeated him. Worse, the fight made Starjun's cells evolve, making him even stronger than before!
Mongul taught Superman his fighting style during the Enemy Mine known as Our Worlds At War. During a later fight, Mongul claims that there's no way Supes can win, because Supes is the student while he is the master. Superman wipes the floor with him, explaining that he knows many other styles, like Rope A Dope.
An early issue of Fantastic Four has the titular team struggling with the Mad Thinker's Monster Android, who was so tough they were only able to defeat it by luring it into the Negative Zone portal. 100 issues or so later, the team takes out multiple androids of this type easily, and later on Sue defeats some by herself.
In fact, many villains were subject to this once Sue Took a Level in Badass, even Doctor Doom underestimated her and she nearly defeated him by herself.
The Dark Knight Rises: When they first fight, Batman treats Bane like a regular criminal, is out of shape, and suffering from the psychological, emotional, and physical consequences being a city's protector. As such, Bane tears him apart. The second time they fight, Batman is fighting with a renewed sense of purpose, knows how to fight Bane, and might actually be in better shape than he was last time (despite the previous fight ending with Bane breaking his back). So this time around, he tears Bane apart.
Batman also learned the Bane was breathing analgesic gas, and knew to attack his mask the second time around.
The Matrix: This is a problem for the superhuman Agents after Neo becomes The One. Even the upgraded Agents specifically created to fight The One aren't even able to land a hit on him and are quickly dispatched with minimal effort on Neo's part. Agent Smith also has this to a certain extent; by himself, he is no stronger than he was as a normal Agent, and is thus far outclassed by Neo. Unfortunately for Neo, Smith now has hundreds of identical copies created by copying over programs and people in the Matrix. Even though Neo tosses them around like ragdolls, the Smith army has collectively greater stamina and Neo is forced to run. Then he wises up and copies over the Oracle, granting him power equal to (or even greater than) Neo in a single body. He didn't think the finishing blow through, though.
X-Men Origins: Wolverine: Victor curb-stomps Logan at the bar, then Logan gets his adamantium and wipes the floor with Victor in their next two fights.
Averted in the book series 1632. At first, the American weapons from the year 2000 vastly outclass the weapons of the time. After research and development, using espionage and the American library for reference, the weapons disparity is greatly reduced.
The Solarian League Navy in the Honor Harrington series has spent literally centuries as the biggest, baddest navy out there. Able to push around any "neobarbs" who got uppity with no problem. In their arrogance over that fact, they never developed much in the way of new technology themselves (so as not to change their own balance of power) and disregarded anything Manticore and Haven came up with as inherently inferior, despite the two star nations' recent Lensman Arms Race. They're learning the hard way just how far behind the curve they are now as every battle they've fought with Manticore has been a Curb-Stomp Battle in Manticore's favor despite being vastly outnumbered every time.
In Isaac Asimov's story "In A Good Cause...", a large alien empire seems to be on the brink of conquering the squabbling collection of human worlds. It doesn't turn out that way: the squabbling had led the humans to refine their military technology and tactics to the point that the first human world to seriously confront the rather stagnant alien empire easily defeated them, even before other human worlds started putting aside their differences to join up with the winning side.
Myrddraal, the minor Humanoid Abominations that act as Elite Mooks and field commanders for the Shadow get this too. In the first book, they're terrifying and treated as Run or Die, basically. In the next couple of books, they're still really tough, but the protagonists get better at dealing with them. Later in the series, they're only slightly harder to kill than Trollocs. Of course, this was foreshadowed in the first book- Moiraine explicitly points out that any even somewhat skilled channeler can beat them without much trouble, and by the midpoint of the series all the protagonists are either quite powerful channelers or have some other ability to put them on that level.
In Worldwar, a race of lizard-like aliens scouts out Earth during the 12th century and spends the next eight centuries preparing for an invasion. Problem is, their technology progresses very slowly, so they arrive on Earth in 1942 expecting to face knights and archers... and run right into tanks, machine guns, airplanes, and The Bomb.
The aliens actually were prepared for ANYTHING they could conceive, and brought with them enough troops and weapons to conquer the expected target a thousand times plus anti-tank and anti-aircraft weapons and enough nukes to glass Earth, just in case. As it was, it was barely enough to force a draw after conquering half of the planet.
Live Action TV
Notable in Buffy the Vampire Slayer. In the first season, the first Big Bad, The Master, was shown as this terrifying, ancient vampire whose history of atrocities was enough to plague Buffy's nightmares and was able to easily imprison and torture Angel in an alternate universe. By series eight in the comic series, both had progressed to the point that a possessed Angel was able to shatter his skull when he was temporarily revived.
In the same vein, the Turok-Han were an ancient and feared breed of vampires who were considered monsters even among ordinary vampires. Buffy's first encounter with one Turok-Han in "Bring on the Night" led to her being bashed around like a ragdoll and nearly getting killed. By the final battle with the First Evil, the Turok Hans' have decreased notably in performance. While the first Turok-Han forced Buffy to use every possible resource to defeat it the second time around, the later Turok-Han seem evenly matched against the newly activated Slayers and even normal humans such as Xander and Dawn. This was Lampshaded by creator Joss Whedon in his audio commentary for the episode, who acknowledged the continuity issue with the Turok Han's powers.
In Doctor Who the Daleks were a serious threat in earlier episodes, but every time the Doctor defeats them, they become less credible; by the end of the original BBC run, Daleks were nearly laughable. See also Depending on the Writer, because sometimes the Daleks really were laughably ineffectual and sometimes the Doctor was just that good.
Then in the new series they're back to being terrifying.
Averted in Stargate SG-1. At first, when humans get Ancient technology, they can curb stomp the Go'auld. Fast forward a few years, and their new ships can ignore the human beam weapons and destroy them.
In the Star Trek series, when the Borg appear first their Cubes are unstoppable even by an entire fleet of Federation ships, and must be beaten by trickery. By the time Star Trek: First Contact comes around, increased fleet size and new technology mean the Cube is far from unbeatable, although it does still take Captain Picard hearing the voice of the collective to find a weak spot to finally destroy it.
Then you have the Voyager series finale, where the titular ship uses technology from 20 years in the future to One-Hit Kill Borg Cubes with the Cubes barely able to scratch the paint on the ship. The Borg end up assimilating the new tech, but due to a virus infecting the Borg Queen, only get it implemented on one sphere that conveniently pulls Voyager inside itself so it can be destroyed from within.
Magic: The Gathering has the skyships Weatherlight (the heroes) and Predator (the villains). When the two battle in Rath, the Weatherlight is outgunned and the heroes only escape through dumb luck. By the time of the Rathi Overlay in the Planeshift storyline, however, the Weatherlight had a more experienced crew and upgraded weaponry, and when the two skyships battled again, the Predator was thoroughly trounced.
Scion: Ragnarok notes that, given how they statted out Garm in Demigod, most players would probably be able to beat him into a fine paste at the God level of power, and advises Storytellers to avert the trope by giving him an appropriate stat boost when he fights Tyr (the justification being that Garm's had plenty of time to level-grind on Scions and Demigods on his way to Ragnarok).
Can be invoked by good optimization tactics in any tabletop RPG that gives the players control over character creation. Will be invoked by Monty Haul gameplay. As such, this trope has the potential to be in most any tabletop RPG.
Its also likely to happen literally. As the players level up monsters that were challenging will become jokes, and monsters that were once too powerful can be crushed beneath the player's heels. And there's the possibility of evil NPCs either not levelling up as fast as the PCs or not levelling up enough to keep up with the players new powers. Some GMs invoke this trope for dramatic effect.
In Captain SNES, everyone in the world of Final Fantasy VI freaks out when Kefka is brought Back from the Dead, up until they find out he's just as powerful as he was the last time they did battle! Unfortunately for him, the heroes had been guided by a player who power-levelled them so badly that Locke killed him so fast (repeatedly, thanks to multiple resurrections) that eventually the biggest complaint was that no one else was getting a turn, and then when Locke proceeds to let everyone else go, they find it unsatisfying to take him down in one hit. Kefka eventually turned the tables by taking the kid who was resurrecting him hostage.
In FreakAngels Mark doesn't exactly forget to level up, but does ignore the possibility that the Freak Angels might have done so too. He's just surprised when Kait disintegrates his sword, but totally unable to cope with Arkady's ability to teleport. Though in fairness to him, the other theoretically heroic FreakAngels didn't cope with it all that well either.
In Kid Radd, this happens to the final boss Gnarl - both while they're both inside the game, and after they both leave.
Crystal:[playing poker] Sweet! Starshine gained a level!
Jenny: I really need to pick a fight with a PC one of these days...
Dragon Ball Multiverse zigzags this, with many of the original series's villains having set up Villain Worlds and not seeing the point in pushing their limits without competition. Freeza's family and troops, Bojack's gang, and Dabura haven't improved at all from their original level of skill, and the Androids are actually breaking down from lack of maintenance. However, Cell's Blood Knight attitude has left him training constantly since the Cell Games (it's implied he could give Mystic Gohan a fight), Buu's been on an all-absorption diet since the end of the series and won the Superpower Lottery to begin with, and Broly's power requires no training to grow.
Parodied in Dr Mcninja, when the Doc easily dispatches a vampire the Alt Text snarks that he had lived 126 years without ever thinking to take a karate class.
The Salvation War has a case of this with the demons. Their tactics haven't changed in centuries, believing that humans could never outdo them. The humans proceed to kill entire armies easily. Later, a character points out that the demons' tactics would have been devastating to humans centuries ago, and they never could have won, but now it's demons with tridents versus humans with guns.
The creator pointed out that they could probably still have pulled a victory against WW2 era armies. The victory had more to do with modern coordination technology, precision artillery, electronic warfare defenses that make their electric attacks a No Sell, and advanced enough technical knowledge to reverse-engineer portal creation than just having guns and bombs.
Cedric in W.I.T.C.H. has supernatural powers that put him roughly on level with the heroines, a nasty Scaled Up form, and a lot more experience than his opponents. Unfortunately for him, said heroines start out inexperienced but quickly become much more proficient with their powers, while he never seems to learn any new tricks. By the midpoint of the first season, he's only a threat if he's brought a lot of mooks with him.