Barry: "[Lucia] knew when [the Tyrant] was nearby!" Leon: Barry, they're always nearby. You got lucky when you only had to fight yours TWICE. Did you hear about Jill's? She lost count, Barry. She. Lost. Count."
The non-comic relief version of the Goldfish Poop Gang. A boss-type monster who you have to face several times (usually three) over the course of the game, though fortunately not in back-to-back battles.
Though, unlike the Goldfish Poop Gang, he is an actual threat each time.
There's a few ways it can go:
The boss flees when defeated, only to come back later (presumably after some Level Grinding).
The player(s) actually kill the boss, only for him to be resurrected later on by some means and come back for another go. (This isn't much different from facing distinct bosses, but may help refine the scope of the story.)
For the first two cases, the same tricks and tactics will usually work to defeat the boss each time — though frequently, the player will not be able to execute the required trick in the early appearances (especially if it's a Hopeless Boss Fight). Alternatively, the boss may announce during a later confrontation that he has gained an immunity to whatever beat him last time.
Any version can turn out to be the Final Boss in their most powerful form, depending on how the boss relates to the surrounding plot; alternately, the decisive final battle against this boss may be held back as a Bonus Boss.
In action games, they often take the form of an Implacable Man. He may end up suffering a Rasputinian Death.
In The Legend of Zelda: Link's Awakening, A Stalfos miniboss in the Catfish's Maw dungeon is the first variety. After you've defeated him once, he seems to become terrified of you, despite popping up to fight you again and again. At one point he steals the dungeon treasure from its chest and leaves a note in its place. You have to kill him to get it.
The DomZ Serpent in Beyond Good And Evil. While the method of beating it remains the same each time, its movement pattern changes each time to reflect the mobility of your overworld vehicle. It's also one of the animals you need to photograph, but if you don't nab it in a fight, it isn't Lost Forever—the skeletal remains of one serpent are found in a cave, and you can photograph them.
Tablet of Graffiti Kingdom turns up in the middle of every other stage until he kills his father and becomes the final boss.
Orochi from Okami. You fight him three times, first time in the present, second time in the past, and the third and final time in the Ark of Yamato. Now technically, Orochi's first and third battles are are (chronologically) after Orochi's first defeat (his second battle - in the past). Another example is the Bandit Spider: An optional creature very similar to the Spider Queen (the game's first boss) fought three separate times in hidden grottos where Multi Mook Melee fights also take place.
Catwoman in LEGO Batman: The Video Game is a recurring boss. She appears several times in one level, and each time you more or less only have to hit her once.
Every boss in the original Devil May Cry is of the first variety, fought exactly three times. Most bosses are the first type, except for the final boss, who is the third type (and his fights are one after the other). The Evil Counterpart Nelo Angelo's fights are spaced out evenly along the plot, while the other three bosses each have their three fights in relatively short (though not immediate) succession. In addition, Nightmare has an attack which forces you to fight weaker versions of killed bosses, allowing them to recur more than three times. Devil May Cry 3 also has Vergil and Jester, who you fight three times each.
A puzzle in Devil May Cry 3 requires the player to defeat bosses from earlier in the game to advance. The puzzle element is choosing which bosses to fight, and navigating the area's Alien Geometries. No explanation is offered as to how these bosses came to be alive again. Presumably a demon did it.
In God Hand almost every boss in the game is fought at least twice. The game also features arena challenges, many of whom involve fighting bosses from the main story. (Including yourself.)
Ryu's Doppelganger from Ninja Gaiden III for the NES is fought twice. Once at the end of Act V and again in Act VI.
In P.N.03, Sonnenblume first appears in a Hopeless Boss Fight at the end of the first mission, then in beatable form at the end of the third. Orchidee, the robo-centipede thing, and Loewenzahn, the doom-buggy, both gain new attacks, Orchidee goes Spider TankOne-Winged Angel after its centipede form is defeated the second time, while Loewenzahn II becomes a robotic phoenix.
Initial D Arcade Stage has Takumi Fujiwara, the protagonist of the source manga and anime. You first encounter him as a Warm Up Boss on Myougi (Version 1-3) or Lake Akina (4 and 5), then later as That One Boss on his home course Akina, and once more as a Final Boss on the last course of whatever game you're playing.
Desann, the Big Bad of Jedi Outcast, is the second variety. His Dragon, Tavion, returns for the sequel, Jedi Academy, as the Big Bad, proving to have been of the first variety. She is now much stronger, and when you think she's done for, you find she's got the tendencies of the third variety.
And she now has a Dragon of her own, who is the second type.
The eponymous monster of the Metroid Prime series shows up as a final boss in all three games, most often in its "Dark Samus" form. In Echoes, you fight Dark Samus a total of three times.
Anna and Gunther in Deus Ex. Anna's a Recurring Boss if you run away from her first boss fight, battling her for real later on. However, the fight's not really hopeless: You can stand your ground and kill Anna, and you never have to fight her again. There's also an earlier scene in which her usual NPC invulnerability is rescinded, though that's really only a boss fight if you opt to kill her while her guard is down. Note that Anna is a Skippable Boss all three times: You can simply not attack her the first time, you might get captured before the second (though there's no reason to do so intentionally), and you can learn a passcode that kills her instantly before the third.
Like Anna, Gunther can be a Recurring Boss. Like Anna's, Gunther's fights are skippable. Unlike Anna, Gunther really is a Hopeless Boss Fight in the first encounter: You either surrender in dialogue or get captured when he kicks the stuffing out of you. You can still use the "kill phrase" trick in the second if you make the right choices in game, though.
Heavyweight enemies in Zeno Clash. They're not the only boss, but they seem to be a good 75%.
Half-Life 2's love affair with Striders. Notably, while they're all exactly the same creature/mech, they fit different boss tropes pretty much every time.
The Makron in Quake IV is fought twice. The first time, he's unbeatable and captures you to be Stroggified.
The Warlord from Unreal appears two times - once in a castle (from where he teleports before you get the chance to kill him) and the second time in a mothership. If you do manage to kill the Warlord the first time, nothing changes - he still appears later on. It was also planned to include him in one of the first levels as a teaser, where he flies away before the player could attack him.
In the expansion Unreal: Return to Na Pali, the Warlord appears once again, but it is explained that it's a different one.
In Halo: Reach, the Field Marshal runs off and sends his Zealot underlings after you the first time you meet him in a cutscene near the end of Winter Contingency, later, you fight him for a moment after he kills Kat in New Alexandria, before he escapes again, only in the last mission is he beatable.
The Big Sisters from BioShock 2 were originally going to be a single enemy that runs off instead of dying when the fight's over, but playtesters complained that this was unsatisfying. The lack of any material payoff in a game where looting slain enemies is a core part of gameplay — especially considering how many resources it takes to bring her down — probably didn't help either.
In City of Heroes, one plot arc has you fighting the Envoy of Shadows (a powerful demon) multiple times. Even if you defeat him, he's still around after the mission. It's explained in-game that in order to send him packing for good, you have to learn his true name; after you manage that, his final Climax Boss defeat signals the end of the arc.
Also, over the course of the late game story arcs, you fight Nemesis several times. Curiously, most of the time your contacts act like you've actually killed him (despite the game being Never Say "Die" the rest of the time), but they always leave the bit of doubt that it really was Nemesis you killed. (And then there's the possibility that it really is Nemesis EVERY time, but his consciousness is spread out over many different bodies. Given that he at one point plans to take over the minds of the entire Rikti race, that's not as crazy as it sounds.)
One player theory is that the real Nemesis died a long time ago and it's just a bunch of robot duplicates running about, with occasionally one of them starting to think that it is the real one.
One story arc also requires that you fight Mary MacComber - and beat her, then the rest of her minions - ten times in a row. Might qualify as a Sequential Boss, too.
The Nemesis system in Champions Online means you actually get to CREATE your own recurring Boss, as well as determine his powerset, personality, minions, and the minions' power type. And if you finally defeat him for good, you get to create another!
World of Warcraft has the Lich King himself as this during the Wrath of the Lich King expansion. Players face him multiple times as they level through Northrend, culminating in a the single-player quest Tirion's Gambit, then the 5-player dungeon Halls of Reflection, and finally the actual raid encounter in Icecrown Citadel.
The Blood Prince Council consists of three vampiric Darkfallen players killed in quests or dungeons earlier in the game, reanimated and empowered by the Orb. Two of them have abilities reminiscent of their strategy from the first time (Fireballs and Shadowbolts for Taldaram and Keleseth respectively), but Valanar has bizarrely developed kinetic energy manipulation.
Nezikchened in Runescape is this, as you fight him three times throughout the course of one quest. There's also Sigmund as well, who is also fought three times throughout three different quests.
Regarding Nezikchened, after that quest, you can do While Guthix Sleeps, part of the larger story arc in the game. At one point, you are tracking down a wizard, and in his miscellaneous diary, he remarks that although the totem poles in the Kharazi Jungle have returned to normal (basically, what you did during the quest with Nezikchened), an ancient demon is still present, hinting that he might be coming back.
Jacoby Drexelhand from the introductory Korthos Island quests from Dungeons & Dragons Online. You first meet him as the NPC who opens the gate for you at Heyton's Rest, is revealed as the collaborator with the Sahuagin and the Devourer Cult in the instance appropriately titled The Collaborator, and after you dispatch him in that quest, he is brought back as an undead wight, who you have to kill again in the finale of Necromancer's Doom.
Break Man who is actually Proto Man in Mega Man 3.
The Mega Man Killers first showed up individually in each of the first four GB games. Then you fight all of them again in 5 GB. And now, after a long disappearance, they're, barring Quint, showing up in 10 as the Special Stage bosses.
In his first appearance, Ballade had to be fought twice before the game ends. Interestingly, his second phase has been completely dropped in future games, with his battles using the second attack pattern, but his original appearance.
Bass in the Classic series. He's your Warm Up Boss in 7, before you later fight him one-on-one in Dr. Wily's first castle stage, then he merges with Treble in the second stage. Then you fight him again in Wily's castle in Mega Man 8.
The Yellow Devil has been so recurring that he's even crossed over some of the sub-series. Along his classic series appearance in 1, 3, 8(as Green Devil), &Bass (ditto), V (as Dark Moon), Power Fighter series and Adventures (as New Yellow Devil); he's also a boss in X5 (as Shadow Devil) and the Zero series (as Rainbow Devil).
High Max of Mega Man X 6 is invincible in the intro stage and requires two particular attacks in order to defeat him when you meet him again. (Unfortunately, you're also able to encounter him later without having acquired the requisite attacks, leading to a Hopeless Boss Fight that merely ends in a Game Over.)
In X5 there's Dynamo, a bounty hunter who is hired to stall the heroes as they try to prevent the Eurasia Colony from falling onto Earth. He teleports out when his health bar runs out, only to reappear a while later until he flees for good. He's also in X6, but only as an optional boss.
And of course, there's the infamous Vile, starting off as unbeatable in his first introduction in X1, only to be defeated in the Big Bad's final fortress. He shows up after being resurrected in both X3 and X8'', fuelled by his hatred of the Hunters and X in particular.
The X-Hunters in 'X2'' are fought a second time in the final fortress, two of three in their One-Winged Angel forms.
Colonel in X4 is fought twice in X's story path, his first battle being replaced by a cutscene in Zero's.
The Four Guardians from Mega Man Zero. Three of them are fought four times (the last time would be in their One-Winged Angel forms), while the fourth Guardian wasn't alive long enough to be seen with a OWA, and the third time he's fought, it was only as a Bonus Boss.
Shadow Man is a miniboss version of this trope in Rockman 4 Minus Infinity. He first shows up in 3 of the Robot Master Stages. He makes his last supposed appearance in Cossack Castle Stage, riding a kite.
Gnasty Gnorc of the Spyro the Dragon games is a special case. He doesn't appear more than once in the same game, but he's appeared in multiple games (the first and fifth). Ripto is the same case, except he appeared in the second and fourth games.
The Legend of Spyro: The Eternal Night has a great number of Dreadwing minibosses scattered throughout the entire game. One is a main boss, the Assassin, whom you fight twice, once in the first level and once in the last. You also fight Skabb twice during the Sky Pirates arc.
Bowser himself is a recurring bad guy in many Mario games. You fight him three times in Super Mario 64 as with both Galaxy games.
Nearly every boss in 64, Sunshine and Galaxy appeared at least twice. And there's Topmaniac from the latter, who appeared FOUR times for no real reason (two normal battles, one daredevil run and one speedrun).
ShellShock from Ratchet: Deadlocked requires you to face him almost five times in the same level before he finally succumbs to you.
In most 2-D Sonic the Hedgehog games, Doctor Robotnik/Eggman is an extreme example of this. Not only is he a boss in every game, but the boss of almost every level therein; other bosses are the exception rather than the rule. He runs away after his vehicle is destroyed, and has a new one ready by the next encounter.
Ridley serves in this capacity for the Metroid series as a whole. He's made in appearance near the end of almost every game in the franchise, and has even shown up twice in two of them.
The only games Ridley doesn't show up in some form are Metroid 2, Metroid Prime 2 and Metroid Prime Hunters. The only enemies/bosses to appear in more games are the eponymous Metroids. Strangely enough, if you count cameo appearances the only non-Metroid enemies that give Ridley a run for his money are Sidehoppers, which are fairly minor enemies and can be hardly considered to be iconic or anything (they appear as enemies in 4 games and have cameos in 2 others, while Ridley appears in 7 games in total).
You must fight Ridley 3 times in Metroid Prime 3: He harasses you while you're using Morph Ball to navigate between towers the first time, then you fight him while plummeting down a shaft, and finally when attacking the third seed, where he's powered up by Phazon and labelled 'Omega Ridley'.
SA-X from Metroid Fusion is the second variety. Some encounters are avoidable entirely as long as Samus doesn't expose herself, but the later ones always force you to run away. It can be stunned with Ice Missiles, but only briefly.
The security robot from Fusion is the first variety.
Metroid: Other M has this flying anomalacris creature called the Rheodigan. Appears out of nowhere, fires seeker missiles at you, and all sorts of crazy shit. After the fourth fight, he finally dies and gives up the Seeker Missiles. In the end of the Playable Epilogue, you have an enemy rush before the final boss. THERE ARE ANOTHER TWO OF THE RHEODIGAN. Thankfully, they die there and then.
Nightmare, from the same game, is fought twice. However, there isn't a lot of action between the two battles, so some could say he's more of a Sequential Boss.
Two of the bosses in Donkey Kong 64, Army Dillo and Dogadon, are fought twice each, their rematches giving more powerful and harder battles. Also, nearly all the bosses in Donkey Kong Country returned later, slightly faster / more difficult, but otherwise near exactly the same.
Deadeye Joe in Contra: Hard Corps, depending on whether the player chooses to pursue him at the end of the first stage or not.
The first Strider has Solo, who you fight twice (three times if you can't defeat it the first one). The sequel has Solo reprise it as a Mini-Boss in two stages (his first fight now being sequential), and has Hien become one in the PSX port exclusive Stage 0.
Midnight Wanderers has Balgoss and Dougar, bosses being fought twice in stage 1/3 (respectively) and 5.
Tsubai in Panzer Bandit has a Mini-Boss fight with a smaller lifebar midway through Stage 5, which he serves later in a full-fledged Boss Fight. Add to that his third fight as part of the end-game Boss Rush.
The 2004 version of Sabre Wulf takes this to the point of exaggeration: you "fight" (or rather, run the hell away from) the titular beast at the end of every level as it chases you back to the start. It instantly kills anything besides you and it in the entire level, and runs much faster than you, but it can't turn around as fast as you can, so you can slow it down by repeatedly jumping over it. Incidentally, even if you trick it into falling down a hole, it'll be back again next level, no worse for wear.
Arma in Demon's Crest, who Firebrand fights three times, each time dropping a different crest as a reward.
The Empress Bulbax in Pikmin 2. She's generally the first boss you'll fight at the start of the game; she reappears much later in two other holes. In your second and third encounters with her, she becomes a Flunky Boss capable of summoning the fragile-but-deadly (to your Pikmin, that is) Bulbax Larvae. While her "main" attack (rolling) remains the same, the addition of Mooks makes you change your strategy.
Perhaps the most notable example is Gilgamesh from Final Fantasy V, whom you fight a grand total of FIVE times, though usually as a gag battle. Each appearance involves humorous dialogue, followed by Gilgamesh making some sort of excuse for leaving and at one point leaving his sidekick to "deal with" your party. During the fourth battle, he whips out the piddly Excalipur, which he'd mistaken for Excalibur, causing Exdeath to send him to the Void. Later, in the void, he recognizes your characters during the fifth encounter and even sacrifices himself to save your party from a later boss.
In Final Fantasy VI, there's Kefka, who started as a joke battle in Sabin's scenario, then a boss battle in Narshe, another short scripted battle at the Cave of the Sealed Gate, yet another (easy) boss fight where you get to play as General Leo, and finally the final boss as a god.
Ultros is fought four times - once in Lete River, once in the Opera House, once in the Cave on Crescent Island, and once in the air.
In Final Fantasy VII, there's both The Turks, who you are forced to fight once, but there are three optional boss fights with them. The Ultima Weapon is also fought several times, but is a Bonus Boss.
Rhapthorne from Dragon Quest VIII. Counting the different people he possesses, you fight Dhoulmagus, then an upgraded form of Dhoulmagus, then Jessica after she's been possessed, then Sir Leopold. And though Marcello resists Rhapthorne, he's still using Rhapthorne's staff against you, so he counts. Then you finally go fight the man himself in tiny baby mode, and then battle two different stages of him in the final boss battle. All told, that's having to beat him eight times before he finally goes down.
Yggdrasil encompasses all of these elements. He's unbeatable in his first appearance, leaves during his second, and transforms during his final appearance. He can be beatable in his second fight, but you have to be max lvl and do it really fast.
You must also fight Kratos thrice and Botta twice, who either don't care if they win or lose or just plain won't stay defeated. You can also face past versions of Kratos, Yuan, and a young form of Yggdrasil again in the PS3 version of the game in a bonus dungeon.
Pronyma and Sheena. The Sword Dancer is faced three times, but he's an Optional Boss.
The sequel has Alice and Decus, each of whom are fought first individually, then later act as one of the penultimate bosses as a Dual Boss.
Tales of Vesperia features Zagi, who uses the first and third forms. You fight Zagi a total of five times throughout the game. (Six if you include the "Sidequest dungeon".) And no matter how many times he's tossed off a boat or had his arm blown up, he just does not back down.
Lampshaded by Estelle and Judith, who, by the final time he's encountered, tell him "Stop bothering us!" and "...Don't you ever die?"
Tales Of Graces features Richard/Lambda. You fight him in his normal (albeit possessed) human form twice, One-Winged Angel humanoid form twice, a vision of Lambda as he first appeared once, and his true Lambda Angelus form as the final boss.
It's also important that Asch was also an Oracle Knight, but was only fought twice. However, that's mostly because of his rolein the story.
Hades from Kingdom Hearts II. When you first meet him, he is impervious to your attacks and you're forced to flee while he hurls fireballs at you. Becomes beatable later, being fought and defeated in the second visit to the Colosseum, then again at the end of two of the Colosseum cups.
In Chain of Memories, numerous members of Organization XIII are fought numerous times. At least in Sora mode - You fight Vexen a third time in Riku mode, and Zexion and Lexaeus are fought only once. But the king of this trope is Riku Replica, who is, over the course of Sora's and Riku's story, is fought a total of six times.
Birth by Sleep has Vanitas who's probably a quarter of the bosses in the game. In Aqua and Ven's paths he's fought 3 times each, including both of their final boss fights. Terra only fights him once, but as a Dual Boss with Xenahort.
Hades is practically a recurring boss throughout the entire series; one of the few villains who continuously pesters Sora (and the keyblader users for that matter) besides Maleficent and Pete. But if bosses who're fought multiple times in the series count as a Recurring Boss, we'd be here all day just reading the examples.
Subverted in thisGCC strip, where the main character laments about having just realized he will need to fight his rival again and again.
In Baten Kaitos: Eternal Wings and the Lost Ocean, Giacomo and his crew appear several times as bosses, even forcing two difficult fights sequentially (to the annoyance of many gamers). They've even got their own theme music, "Chaotic Dance."
Giacomo also appears several times in Origins (complete with a remixed "Chaotic Dance"), though he's rather less threatening and stops showing up near the end of Disc 1.
In Baten Kaitos Origins, the heroes have to face one boss, the Lord of the Lava Caves, three times in about ten minutes of game. Notable because the (otherwise serious) heroes hang lampshades all over the encounter, complaining bitterly about how difficult the boss is and how annoying the repetitive fights are, and even stomping spitefully on his corpse when he goes down for good.
As pictured, Jr. Troopa appears multiple times in Paper Mario. He's actually a fairly difficult and ingenious foe, adjusting his weaknesses with each encounter, but Mario and his companions don't take him seriously at all, and he's often the butt of jokes. In the final dungeon, he actually prevents another boss The Koopa Bros. from recurring in order to get in another shot at you.
Another recurring Paper Mario boss is the "Invincible" Tubba Blubba (until you find and defeat the real boss his heart, after which Tubba himself is a Curb-Stomp Battle).
Similarly, Popple is fought four times in Mario & Luigi: Superstar Saga, though only once by himself. Bowser is fought four times as well: once as a Tutorial Boss, twice as "Rookie" alongside Popple, and once when possessed by Cackletta.
From the same game, there's Doopliss, whom you have to fight over and over again as you run back and forth from Twilight Town to Creepy Steeple.
Midbus fulfills this role in Mario & Luigi: Bowser's Inside Story, being fought three times total. This is also how many times you fight Bowser, which is strange when you consider that he's one of the playable characters. One of those times is as a Bonus Boss, however.
One of the bosses on Ellen's path in Persona 2: Eternal Punishment is a recurring vision of her "stalker". He attacks several times, becoming more and more damaged and bandaged up each time.
The Wild ARMs games use this constantly, with the third game being the worst contender (practically every significant boss is fought at least three times). The fourth game is the only one that avoided this trope, by giving the main antagonists so many members you only need to fight each of them once; on the other hand, this made half of them immediately forgettable.
Fassad/Yokuba in Mother 3. He crosses paths with you about four times, though you only fight him twice.
Jin and Takaya, of Persona 3, after the fight against them before fighting the Hanged Man, proceed to jump off a bridge. They come back.
Breath Of Fire III has the "Horse Brothers" Balio and Sunder, a Dual Boss: the first battle against them is unwinnable, the second can be won (but can also be lost without getting a Game Over), and it's in the third battle where you finally get rid of them for good. Garr as well, being fought twice (the first of which is also unwinnable).
Saren in the first game. You fight him once on Virmire, but he escapes. Then you fight him again on the Citadel. Depending on if you convince him to commit suicide or not, you may not have to fight him the first time, but you'll definitely have to do the second fight when Sovereign burns out the organic parts of his body and animates his cybernetics.
In the Rockman.EXE games (Mega Man Battle Network), every game after Battle Network 2 had Forte (Bass) as a 2nd-to-last boss OR as a secret final boss. In Battle Network 2, you would have to fight him before you fight Gospel, and later, you fight his real version in the secret area, which you cannot "jack out of" until you get back to the point where you entered it. In Battle Network 3, you fight him before Alpha, as well as in yet another secret area where you actually help fund his recovery in a bug frag trade machine. In ,4 he appears in Undernet 5 after beating the game about 3 times and disturbing his "statue". In 5, he is in yet another secret area called the Nebula Area after completing what they call a "liberation mission" in area 6 and getting a time between 25-40 seconds busting the navis in that area. In 6, he appears in the Undernet (where he is in a stone monument) and then a harder form in the Graveyard area, then a supercharged version in the Underground area, in which he sports a Gregar (Or could also be Gospel, as they were both made from bugs, much like the Bass from Network 2) head or a Falzar head depending on your version.
In every single game, you also end up having to fight some, if not all of the storyline bosses again later in the game.
When you play Lufia series, expect to fight Gades at least twice. In the first time, you can't beat him (not without doing way too much grinding anyway.) The second time is when you fight and beat him thinking he's final boss, there's also likely the third time where he's resurrected and fight you in the final dungeon as a part of a Boss Rush.
Solt and Peppor in Chrono Cross are the first type. Your first several fights with them serve primarily to teach you about the combat system as they make horrible tactical mistakes. Eventually, you fight them in a sidequest and they're actually almost difficult.
The Asylum Demon, Stray Demon, and Demon Firesage in Dark Souls are practically identical, though the Stray Demon and Demon Firesage add powerful fire attacks to their repertoire.
And Kirk, Knight of the Thorns, is the only NPC to invade you more than once.
Pison in The 7th Saga. Combined with Palette Swap, as he becomes Red-Pison (yes, they actually call him this) and Metal-Pison.
Xenogears has the persistant Ramsus. Swearing to defeat the hero we fight him, on foot, in a submarine type mecha, in his Ace Custom mech, in his Ace Custom mech transformed into an Omnigear, and finally in the omnigear of the Big Bad (Ramsus is not the Final Boss, he simply no longer needed it and Ramsus can use any Omnigear due to his genes). With him for all but that last two is his assitant Miang who we also fight twice on her own (one time she's in disguise so the Party doesn't know its her). Ramsus also has a subordinate Domina, and her squad of 3 other soldiers. You fight Domina in a ship, in a submarine mech, in her own mech, in her own mech alongside her squad, her entire squad on foot, and finally in one giant mech piloted by all 4 of them. All these bosses are either with Ramsus himself or on his orders.
In NetHack, once you Either kill the Wizard of Yendor or perform the Invocation Ritual, the Wizard of Yendor will, even if you kill him, every number of turns, be able to resurrect, and is guaranteed to reappear on the Plane of Earth.
The Gradius series in general seems to thrive off the Recurring Boss concept, as many come back in theme if not outright in a Boss Rush of subsequent games. The original Big Core is still the Recurring Boss champion, rivaled only by Tetran from Salamander.
All but one of the R-Type games has included Dobkeratops as a boss. Gomander and its invincible Outslays make frequent appearances as well, as does Gaines, the human-shaped robot with a BFG who seems to exist to get killed halfway through the first stage.
Battle Garegga has Nose Lavaggin (Stage 1 boss) and Mad Ball (Stage 2 boss) appear again in Stage 5. And then the endboss of Stage 5, Black Heart, makes a second appearance in Stage 7. And in the Spiritual Successor, Armed Police Batrider, Black Heart not only appears in its original form, but also a second time within that game in its mk. II form!
Several bosses in Touhou come back with different bullet patterns, either in the same game or in later games, but the prize for most recurring boss goes to Rin Kaenbyou, who shows up in Subterranean Animism as the stage 4 midboss (twice!), stage 5 midboss, stage 5 boss, and stage 6 midboss.
Another recurring boss is Nue Houjuu, who is the Stage 4 midboss, Stage 6 midboss, andBonus Boss of Unidentified Fantastical Object, and the Extra Stage midboss in Ten Desires.
In Legendary Wings, save the Final Boss, all other bosses are simply just variations on one another, with later ones having more cannons.
Liquid Snake in the original Metal Gear Solid and Sons of Liberty serves as a mix of the second and third varieties. He is defeated in a Hind D, Metal Gear Rex, fistfight, and Jeep before finally succumbing to FOXDIE, and in Sons of Liberty, he is reincarnated as Revolver Ocelot's new arm.
In addition to Liquid, the player must fight against Sniper Wolf and Vulcan Raven twice in the original MGS. A more subtle example is Revolver Ocelot - he flees after the fight and later returns to tortures Snake.
Ocelot is fought in 1, 3, and 4. Oddly enough, despite his importance in 2, you never get the chance to fight him.
Metal Gear Solid 2 also has Vamp, who comes back from a cutscene death, his Harrier being shot down, a firefight, and a sniper duel in that order.
Not to mention that in Metal Gear Solid 4, his boss battle requires you to use a special syringe to finish him, or else he'll keep coming back to life.
In Resident Evil, The Tyrant pulls a Back from the Dead version, appearing as both the penultimate boss and final boss - unless you burn his body after the first time.
In Resident Evil 2, William Birkin (aka "G") transforms from a simple overdeveloped humanoid in his first encounter to a hulking, deformed monster in his last form (for a total of 5 fought forms). Mr X is also encountered several times, but you're only forced to fight him once.
In Resident Evil 3 Nemesis, you usually have option of fighting or running from the titular Nemesis. If you defeat him in one of the various optional ways, you can acquire two useful weapons, but running doesn't cost anything if you're fast enough. You only have to actually fight him three times: in the middle of the game, near the end of the game as the penultimate boss, and as the Final Boss.
Resident Evil 4 has two odd examples. Saddler is fought twice, but in different scenarios (he's the final boss for both Leon and Ada). Krauser is also fought twice: once in a QTE sequence and then several times in succession in chapter 6-2. He then proves to be Not Quite Dead in Separate Ways.
Silent Hill's most famous monster, Pyramid Head, must be fought several times. The first time, he will leave after either A) a predetermined number of bullets are unloaded into him, or B) a predetermined time limit runs out (shooting him makes the clock run down faster). The second time, you must escape him by running down a very long hallway, and you can slow him with bullets but not kill him. The third time you see him, you just have to run around him in a giant maze. And, as the ultimate slap-in-the-face, in your final battle with him (and this time, he brings a friend), he kills himself before you get to finish the job.
Wiegraf in Final Fantasy Tactics: the first time you fight him, he runs away; the second time, you mortally wound him and he makes a Deal with the Devil to keep on living; the third time, he's been completely taken over by the demon, and the first part of the battle is a Duel Boss in which you have to defeat his human form before he drops his disguise.
Also in Final Fantasy Tactics, Gaffgarion is fought three times; the first time, he turns on you in the beginning of the battle, the second is a normal fight, and the third time is a pseudo-Duel Boss (you have can still use allies in the fight, but they're trapped in another area until you use a switch to open a gate). In War of the Lions, Argath (Algus in the PS1 version) appears a second time late in the third chapter. Most of the Temple Knights, Elmdor, Celia, and Lede are all also fought twice.
Celia and Lede are fought three times. Well, if you count their first apperance (Castle Rooftop) a 'fight'.
Pretty much every boss apart from the final bosses in the Super Robot WarsOriginal Generation, though you can shoot them down before they retreat if you reduce their hit points to just above the point where they'd retreat, then use a really powerful attack.
Gharnef in Shadow Dragon is present on the map midway through the game, and you must simply survive him because it is a Hopeless Boss Fight without Starlight. The second time, you can fight him for real after picking out the real Gharnef amongst his doppelgangers.
And, in fact, he can be skipped. In the original NES Fire Emblem, this can result in the game becoming Unwinnable. In the DS remake, if you skipped him and Tiki is dead, then you get sent to chapter 24x, where Nagi will join the party and Marth gets a weaker Falchion.
Galzus plays almost an identical role as the Black Knight: mysterious, frighteningly deadly One-Man Army whose occasional appearance forces your party to run in the opposite direction. He's not invincible, but for the better part of the game he's close enough to count. Mercifully he can be recruited near the very end without having to deal with him directly.
Saias turns up a couple times during the game, but as less of a boss and more of an incredible nuisance - thanks to having 10 authority stars, his mere presence pumps up the entire enemy force into Demonic Spiders until you do something to make him leave. He also is recruitable late-game, but by then he has lost the overpowered buff.
The Black Knight from Path of Radiance appears on the map a total of three times throughout the game, but you don't possess the means to damage him until the third. The first two, he must be avoided, as he can easily kill anyone who steps into his attack range. In the sequel, Radiant Dawn, he appears as an enemy twice, and can be killed both times, though doing so the first time is both dangerous and pointless, since there is no reward for defeating him and you will be unable to recruit another character later in the game if you do.
Unknown RivalVyers, the Dark Adonis Mid-Boss from the first Disgaea is fought a total of five times. Though he's treated like a Goldfish Poop Gang in-story, he's actually a legitimate threat every time.
Disgaea 2 has Axel, the Dark Hero. He is not, as his name may imply, a vicious murdering bastard, but a former rock star. Mid-Boss also makes an amusing optional cameo.
Several bosses in Tactics Ogre, depending on which path you go through.
Let us Cling Together:
On the Chaotic path, Oz, but this fight with him is a bit out of the way. In the neutral path, he doesn't escape.
You fight Ganb throughout the entire game, with an optional way to recruit him in Chapter 4, along with several of his monsters.
Martym in a sidequest. He dies for real around the final boss.
The Knight of Lodis:
You see Nichart several times throughout the story and you know you'll have to fight him... but then you finally do, while he taunts you with a nice spear during the fight. Except that when you beat him... he doesn't drop it, and he runs off with it. You do face him for real later on, but by the time he drops it, you might have had something better by then.