The giant black pig in Wind Waker is also immortal and also deals out more damage per hit than the final boss of the game. The other two pigs are only half-immortal; you can't kill them, but they die anyway.
The archetypical "piece" of a character is the Metool/Met helmet from Mega Man. Metools resemble a face wearing a construction helmet. While he could be beaten easily enough when he peeks out, with his helmet down he deflects all of Mega Man's attacks (except for latter Mega Man games starting in Mega Man X 8, where the characters have ways of getting through that defense and flip the Met over, exposing their vulnerable undersides.) Has led fans to wonder what the heck those helmets are made of, and why doesn't Dr. Wily just make a robot out of it?
In Mega Man 6, using the Power Armor mode of Rush armor lets you use a charged up punch to destroy a hiding Metool.
In MS Paint Masterpieces, a webcomic retelling of Mega Man, he did. It also goes on to say that the armor works by spreading the force of attacks and sending it around their body. Since Enker has multiple plates of armor, overloading him with energy while he has no way to get rid of it makes him explode.
Enker was actually a boss in the first Game BoyMega Man game. Normally completely invulnerable to all weapons, one of his moves absorbs shots from Mega Man's standard Arm Cannon into his sword and unleashes a wave of energy as a counter, and only then do they damage him.
Gabyoalls/Spines are unaffected by all weapons save a couple. They're those low, disk things with two spikes that move faster when Mega Man's on the same platform. Also a spiny.
In 3 (DOS), there are turrets randomly placed around the levels, usually in platform-heavy sections. You can't destroy them, no matter how hard you try or with any of your special weapons. All you can do is stand in a safe place and memorize their patterns, and hope to dodge their insanely fast bullets/lasers. There is no "or".
The concept arises again in Mega Man Legends with the Servbots, mostly incompetent flunkies to the game's Goldfish Poop Gang. Completely invulnerable to all forms of damage. In the spinoff game The Misadventures of Tron Bonne you can exploit this by sending them into otherwise fatal dangers to retrieve treasure.
They're not completely invulnerable though. You can knock them out. They will be back to normal once you return to the same room however.
The Mets in the Mega Man Battle Network series, while still impervious to most attacks while hidden under their helmets, can be destroyed with any of a number of attacks that can penetrate guards. The Appull viruses in the fifth game, however, are completely incapable of being harmed by direct attacks while closed up, even ones with the aforementioned property.
Super Mario Bros.
The original Super Mario Bros.. It had the Fire Bars and Podoboos (fireballs), the latter being listed among the enemies in the manual (so not merely a trap).
Podoboos can be killed by the Starman. They even have a set amount of points they give by doing so. However, they only exist in maps where there are no Starmen, so the only way to do it is by hacking the code.
In The Lost Levels, there is one castle where you have the opportunity to kick a Koopa shell at one. You get points for the kill, but a new one spawns immediately in the same spot.
Super Mario Land and Super Mario Bros. 3 had the trap-enemy Rotodisc, which could be killed in the latter game by using the Tanooki suit to turn into a statue and fall on it at the right moment. Super Mario Bros. 3 also had Jelectros and Munchers, which were truly invincible, but completely stationary.
This game also is the first appearance of the Dry Bones, who will get up after most attacks. Only invincibility, or rare powerups (the Hammer Bros. suit or the Tanooki suit) could defeat them permanently. In later games, Dry Bones varies in how difficult it is to kill.
Boo Diddly as well, although they can be taken out with a Starman or with the Hammer Bros. Suit.
Super Mario Bros. 2 has "Phanto", who begins chasing you as soon as you pick up a key. However, he stops chasing you once you put the key down. He'll start chasing you again when you pick it up, so it's mostly a game of either out-running him or drop-and-pick cycles.
The GBA remake lets you kill off Phanto if you managed to snag a star.
In the original you can kill him by throwing the key at him. He'll come back, though.
Thanks to a glitch, if you repeatedly throw vegetables or enemies at the stationary key you'll eventually hear the 'enemy made dead sound', and he'll be nowhere to be found when you pick it up.
Super Mario Land 2: 6 Golden Coins has invincible stars (not stars that turn you invincible, stars that are invincible and will kill you). Like Jelectros, they only appear in one stage, a frustrating auto-scroll. Unlike Jelectros, some can move. It also has Gordos, but they only shake a little when Mario comes near them and are not hostile.
In Super Mario World, Boos and Big Boos can be killed by sliding down a hill at them.
In the GBA remake, you can defeat Torpedo Ted by playing as Luigi, bringing a Yoshi into the level, and having him eat other enemies and spit them at the Teds.
Eeries (blue dinosaurs in ghost houses) can only be taken out by a starman.
"Invincible" Koopa Troopas are claimed to be this in the manual, they result when a shelless koopa goes into a yellow shell and flashes like when Mario has a starman, and although they are fairly hard to kill, a starman easily takes them out, and they can even be taken out by a spin jump, a Yoshi jump, or when eaten by Yoshi he can gain all three shell powers, making them a Fake Ultimate Mook in reality.
Whether they hop or march, Tap Taps from Super Mario World 2: Yoshi's Island are virtually indestructible. The only way to get rid of them is to knock them into a bottomless pit or into lava or use a fire Watermelon or Ice Watermelon. Sure enough, when you face Tap Tap as a halfway boss, you have to knock it into the lava under the arena.
If there are several, you can knock one into the others to kill them.
Spitting or rolling a Pill Bug at them (like in 1-7) is one of the few ways to deal with them.
You'll face another one as a sub-boss in a scrolling level. Unlike the boss fight, there's no lava - only apparently bottomless pits. If you knock him in, he'll eventually jump out again.
Super Mario Kart had invincible Thwomps on Rainbow Road. Touching them made you spin out and lose coins. Even the Star item does nothing to them.
Mario Kart 64 had the same thing with Chain Chomps, although they only appear on Rainbow Road.
In fact, Chain Chomps are this in every Mario Kart or any Super Mario Bros. game for that matter, with the exception of the RPGs. Which has its own exception in Paper Mario: Sticker Starnote They can be harmed by first strikes (as they pierce armor), however they have way more health than what a first strike can ever deal, and leaving and re-entering the battle only builds it up. However, you can sometimes get rid of them by stomping the post they are chained to into the ground and their original appearance in Super Mario Bros. 3 also has an Easter Egg where they eventually break their chains if they yank it enough times, but considering how long it takes for them to do so and the fact that all stages have time limits, it doesn't have any practical use.
Paper Mario had the "Invincible" Tubba Blubba. He can only be defeated after his heart and body are reunited.
The Spiny in Paper Mario: The Thousand-Year Door can roll into a ball and make itself completely immune to damage. Its upgraded version uses the invulnerability time to boost its power then attack before uncurling itself.
The Iron Clefts are entirely invulnerable to damage. The only thing hard enough to pierce their defense... is each other. Kid Yoshi is required to beat them, as he can swallow and spit one Cleft at the other.
Gordos and Munchers in the Something series. The Munchers even get a level, Hungry Vegetation, to themselves.
As of Kid Icarus: Uprising, Plutons CAN be defeated, but they move so fast that it's rather hard to do so; plus they run away after a while, taking your stolen items with them. Instead, the newest Invincible Minor Minion is the Orne, which is not only invincible, but touching it is an instant death. Only the Three Sacred Treasures can kill them, and you use them only in one okay, two chapter.
Gordos from the Kirby series are completely indestructible, even if you run into them with invincibility activated (which normally kills every other enemy in the game, including bosses). Gordos could be destroyed in Kirby's Dream Land, but the method for doing so was only available in the boss rush level and is unavailable in all future games, where the boss rush is separate from levels. Kirby's Dream Land 2 featured a boss that took on the properties of a Gordo but had to sacrifice invincibility to actually attack.
Shotzos as well. However, unlike Gordos they follow more the rules of gravity, so you can send one down a bottomless pit if it's standing on a breakable block. But that is less common than how often you can have a Gordo fly off-screen. Also, in Kirby's Dream Land, it is possible to destroy them with invincibility, but it takes some time and Kirby must stand in them.
Batamons in Kirby's Dream Land 3 are technically killable, but it's very hard to considering how little opportunities you have to do so. Mostly, they just happily march around behind solid walls.
Earthworm Jim had a couple, but the most remembered ones are probably the big brute cats in the Down the Tubes level. They can't be killed by anything except plasma, and there is typically a hanging ledge above the area they patrol. You usually have to hang onto said ledge and pull your body up to avoid detection from these guys.
MediEvil 2 loves these, examples include the police officers, the vampire girls and the Mullocks.
An archetypal enemy in Castlevania is the "blood" or "red" monster, usually a skeleton. These enemies never die permanently - they simply collapse into a pile of bones, much like Dry Bones above, and get back up a few seconds later. Castlevania: Portrait of Ruin actually gave two ways for the player to kill Red enemies... one a special spell with a casting time so long that the only time you'll ever cast it is when it's required by the plot, and another a special weapon obtained by a late-game quest, when you probably will never see such an enemy again and wouldn't really care about the damage from any you do chance to encounter. Oh, and they give mediocre experience if you do take them out. You could also kill them with Spyha's ice spell in Castlevania III. Meanwhile, Castlevania: Curse of Darkness has an Innocent Devil that will randomly cast a spell that will destroy one undead monster onscreen, even the red skeletons.
The skeletons in Undying were the same way, they'd always get back up after being taken down with conventional weapons. The only way to lay them to rest was to cast Dispel on them while they were standing.
The blood skeletons in Terranigma function the same way. However, if you dish out enough damage, they stay collapsed and vanish offscreen.
The giant skulls in Castlevania: Symphony of the Night's inverted castle have the standard "not phased by anything" invincibility, although you can use Soul Steal on them to heal yourself.
The skeleton in level 3 of Prince of Persia. The only sure way to get rid of it was pushing it down a deep pit. The Super Nintendo port added reviving skeletons as in Prince of Persia 2, and a crushing trap to finish off the level 3 skeleton.
The skeletons in Prince of Persia 2: The Shadow And The Flame could be defeated, but, like Dry Bones, they would get up a few seconds later. Two special enemies are completely invulnerable: the skeleton on the Rope Bridge (which falls victim to a scripted event), and the floating Flaming Sword.
The living pipes in Rusty Bucket Bay not only can't be killed, but they can hurt you when you're using Wonderwing, which is supposed to make you invincible (though that part could just be game designer oversight.)
Some of the enemies in Banjo-Tooie are impossible or all but impossible to kill. Being able to kill them wouldn't help much, given the speed with which enemies respawn in Banjo-Tooie.
The Rippers of Metroid can be frozen, but not destroyed. (Except with the Screw Attack or Shinespark.)
Since the first game was basically H.P. Lovecraft brought to the computer screen, MOST enemies were either undefeatable menaces you had to avoid, or require so much ammo that you're generally supposed to trap or avoid them instead of defeating them.
An effect somewhat undermined by the substantial stunning effect of player melee attacks, which allowed a player with good timing to brutalize said abominations through repeated bitch slaps.
Tyrian would make some of its later boss battles tougher by introducing a small but invincible enemy with good firepower but extremely poor targeting ability. Sounds pretty par for the course, but it ran around the bottom of the screen and shot upward, forcing you to evade fire from at least two directions.
World of Warcraft has The Cleaner, a black demon who suddenly spawns (Sometimes in groups!) if someone besides the one undertaking one of two particular quests is interfering with the goals and mobs involved. This has lead to some very creative griefing.
Wintergrasp was home to an invisible enemy that would sometimes attack players. While it dealt little damage, it would also cause the target to be stuck in combat while in the zone. It was actually possible to go back to Dalaran and get killed by the guards for being in combat... in a sanctuary zone! This was most likely a bug and removed soon after the introduction of Wintergrasp.
Another bug-induced case of this trope has to do with how mobs react to damage. If they cannot reach the attacker, they'll start evading every attack. This, combined with mobs occasionally becoming stuck, can cause random enemies to be invincible to all damage until the next server reset (although they can't attack anyone, either).
There's also a version where they become able to attack from a distance but are always too far away for the player to attack.
In the original Blasted Lands there were mobs specific to quests in the area. Without a specific quest item they could be damaged to near-zero health and then turn immortal.
Silent Hill 4: The Room has Victims, the lingering ghosts of people killed by "The Man in the Coat". They cannot be destroyed completely, and attacking them only stuns them for a few minutes at best before they get right back up and start chasing you again. Just being near them causes damage to Henry (he'll put a hand to his head and the screen will flash whenever he gets too close). While Saint Medallions and Holy Candles will temporarily ward them off, Saint Medallions eventually break and become unusable, and you'll need all the Holy Candles you can lay your hands on once the Otherworld begins infecting Henry's apartment. The best line of defense provided to you are the Swords of Obedience — there are only five in the entire game, and you're required to use one against a specific Victim in order to progress.
The Rawshocks from Shattered Memories are a subversion in that they're literally the only enemies in the game.
Half-Life 2 has a scene where you're near a lighthouse and the Combine is shuttling soldiers in on dropships. The only weapon in the game that can destroy the dropships themselves is a boat-mounted machine gun, which you had to abandon several hours ago. Even though the dropships are fitted with anti-personnel weapons, they return to base after unloading their troops, only to be replaced by not-invincible-at-all gunships.
The sentry turrets in the game can only be defeated by knocking them over either by throwing a grenade or shooting them from the side with enough force. You can't actually kill them. They will resume their function when placed upright.
You can also defeat them with either fire mode of the gravity gun.
Schroedinger from Hellsing has the dubiously enviable ability to teleport into enemy headquarters, be thoroughly dispatched via BFG, and reappear next to the Major to report. He later seems to have redirected his abilities towards causing existential crises in those who consume him.
In Tales of Phantasia, there is one enemy in the Moria Gallery area, known as 'Urchin', that takes the form of a tiny green worm. However, the green worm is both practically indestructible and very dangerous— it's able to deliver 9999 damage to any character it touches, killing them instantly.
Except Arche, who flies. Sucks to be the party that decided not to include her.
And even then, you would have to have packed a specific item, and be fast, to beat it; the Mah Jong chip, which needs to be made out of yet ANOTHER item.
In Super Smash Bros. Brawl's adventure mode, Jyks move in a certain pattern, damage you when you touch them, and cannot be hurt. They still count as enemies, though.
In Cave Story, Basil races back and forth across the bottom of the Egg Corridor and can kill you in one hit. You can't kill Basil.
There's also Rolling in the Sacred Grounds. Two of them accompany the Heavy Press during the fight with it.
In the first Halo, Cortana will summon invincible marines, and seal the doors, if you kill Captain Keyes in the first mission. You can unload every round in your gun on them, and they'll still be fighting you. Strangely they still bleed, so you can have situations where the marine you're fighting has a gallon of blood at his feet, but strong as ever.
Iji has "Blits", feral chunks of nanomachines that eat other nanomachines. Only one weapon in the entire game (the Null Driver) can kill them, although one log comments that it is possible to launch them into outer space and they'll eventually starve into... "whatever it is, it's not recyclable."
The Bubble Bobble video games have (up to two) Baron von Blubba/Skel-Monsta, an invincible whale skull which chases the protagonists when they cannot defeat all of the enemies in a level. He has been promoted to SequentialTrue Final Boss status in two games.
Impossamole: Many of the Goddamned Bats and Demonic Spiders, including the sword guys in Orient, the swarms of ghost pirates in the Bermuda Triangle, and any underwater enemy. The Amiga/C64 version has both killable and invincible variants of many mooks, such as bats and skeletons, and they're hard to tell apart.
On the higher difficulties in the 3D Ys games, in addition to the color-coded enemies, there are black enemies that are completely invincible.
In the first Commander Keen trilogy almost all robotic enemies were impervious to damage, even the ones that could only push you around. In the second, most unkillable enemies were the tough rather than minor ones, but the sneaky rocks might count for only being vulenrable when they were already jumping at you.
The sneaky rocks were also vulnerable while they were walking around. To kill one, all you had to do was stand far away, shoot at him and immediately turn your back on him. He'll open his eyes just in time to see that neural stunner shot approaching before it hits him square in the face.
The time-traveling FPS Darkest of Days has Opposition Agents, enemy time travelers equipped with futuristic weapons and armor, not to mention energy shields that are completely impervious to the period Civil War and WWI era weapons you're equipped with. Whenever they show up, your only option is to run like hell. Killing "blue aura" characters also causes them to teleport in to kill you, as a sort of Video Game Cruelty Punishment.
Later in the story, an upgrade becomes available that lets you kill them outright, even with Civil War-era weaponry. They're difficult to fight with period weapons, but doing so can be very helpful.
The original game has Stop and Go Station, a level designed entirely around invincible enemies. Rock-Crocs (Kremlings made of stone, with glowingred eyes) infest the mineshaft, pacing back and forth for all eternity. Get in their way, and you're toast. The only way to deal with them is to touch the floating barrels to get them to change from a green "GO" to a red "STOP", which causes the Rock-Crocs to fall asleep. This only lasts for a few seconds, so you must race from barrel to barrel to avoid getting hit. It's not really that difficult, but is infamous for being one of the scariest parts of the whole series.
In the Japanese version, these enemies can be defeated with Donkey Kong's handslap.
Similarly so was the skeletal kremling phantom, Kackle, that you find in the mineshaft level of the haunted woods area. This guy is more or less invulnerable to any attack or thrown object you have (not that you could throw anything since you meet them in the middle of mine cart tracks) and will kill you if the timer above you runs out, which is easy since they chase you for portions of the time you're in the cart. The only way you can avoid being killed by them is by beating the time you get from the beginning of the phantom's chase portion (marked by a door you enter) and make it to that portion's "exit" (another door) before time runs out. If not, that phantom will automatically kill one of your Kongs.
The blood-red piranha, man. Most underwater enemies are unkillable unless you ride/are a certain animal buddy, but the blood-red piranha is both VERY fast and out for your blood. Much horror was had.
In a certain underwater stage in Donkey Kong Country 3, a snook, not unlike the aforementioned piranha follows you around, and it has a gimmick. It starts out blue, then as it gets hungrier, it will turn purple, pink, then red (which it then attacks you). It would stay full as long as you manipulated it to eat the clownfish in the level, and not the urchins. If it ate an urchin, it would suddenly get a level hungrier. Not that making it eat urchins is a completely bad idea, one blocks the route to a bonus stage.
In The Godfather: The Game, you may occasionally encounter mooks who you can't touch at all even though their stated rank is below what you may be routinely slaughtering by then. Fortunately they almost never show up in real combat situations.
Thunder Force IV had these in the lava cavern stage. Part of a larger mook, these things would break off once destroyed, and then orbit around the player character, blocking your shots. The only way to defeat it was to lure it into the walls, doing collision damage to them and eventually killing them.
In the "Siren" series of games, every enemy in the game (the "Shibito") are undead and cannot be killed by conventional means; at best you might pin one down by staking them to the ground under the right circumstances, bury them alive, or something similar; only a couple of characters ever gain access to anything paranormal that lets them destroy them for good. Every other time, you can only stun them. Shoot them as often as you like or smack them with a melee weapon, and they only temporarily go catatonic until they inevitably heal themselves minutes later.
Forsaken plays with this trope in the Space Station level. On your way out, there's a little mouse droid roaming one of the rooms. Mo matter how much you shoot it or what you shoot it with, it will not die. The game will display a message asking you if this little critter is really that annoying that you feel the need to kill it.
Left 4 Dead had a glitch that would occasionally cause a random Common to become invincible. As if that wasn't bad enough, the AI teammates didn't even notice that Common anymore, and it could kill them. The only was to escape would be to shove the invincible zombie into a closet, and then run. Luckily, this glitch has been patched.
Eversion's rock monsters are completely immune to any attack at all, and only pause for a second when you hop on them. And in X-8 in the newer versions, the regular mooks can only be stopped for a short period of time before they regenerate. Not respawn, regenerate.
In Berzerk, if you hang around on a level too long, Evil Otto (an invincible smiley face) shows up and homes in on you, forcing you to move on or die.
Smash TV has faceless drones that behave basically the same way.
In Pathways Into Darkness, Banshees are impervious to physical attacks, while the Green Oozes and "Giant Purple Hellbeasts" encountered on "Earthquake Zone" are completely invincible. The Oozes avoid you if you consume a poison potion.
From Purple, there is a family of rolling barrels, trashcan mooks and spikeballs in the sewers. Of them three, only barrels can be destroyed using the moon item.
Dead Rising 2 features looters that are only marginally tougher than zombies - except if they're behind the counter of their stores (which somehow makes them invincible.)
Bug Only one that's actually an enemy as the other "invincible" enemies are traps of sorts. The spiny lizards of Reptilia could not be killed via any means. Not even the Zap Cap, or Stunt Bug would even touch them. Your only option was to avoid them like the plague.
The Skeletons in the Catacombs in Dark Souls can be killed, but they'll keep resurrecting until the nearby necromancer is slain. They can also be permanently destroyed if they are slain with a Divine weapon.
Some of the panels in Parodius have so many hit points, it's impossible to kill them before they leave the screen. Gokujyou Parodius takes this up to 65536 by giving us the 16-Bit Block.
Perfect Dark Zero's Spiderbots are invincible in the later levels, and will constantly pursue you if alerted, until their sensor is destroyed.
MapleStory had one dungeon with two invincible monsters guarding a platform that do enough damage to OHKO any character three times over. The correct solution was to make a thief sneak past them. The OTHER solution was to make a knight and stuff all of their points into the otherwise useless HP stat so they could endure a hit from them, then use the defense-ignoring damage reflect skill to hurt them each time they damage you until they finally go down. There was absolutely no point in doing this beyond the novelty of it.
Fallout: New Vegas: Dead Money has Ghost People, who can only be temporarily knocked down unless decapitated, dismembered, or consumed by Dog, and Holograms, which are entirely invincible to physical attack, although some can be hacked or have their emitter disabled.
In Gojira-kun, Hedora is the only monster that can't be killed by Godzilla's Megaton Punch, only pushed back a little.
One type of creature in Magic: The Gathering is characterized by being low power, low toughness, fairly cheap to play, and either hard to kill or easy to somehow return to the battlefield after being killed. Skeletons are particularly prone to this. Darksteel Mutation is another example which can be used both offensively and defensively, turning some useless creature into an unkillable blocker, or turning an enemy's most powerful monster into a harmless bug.
The Mollusks in Shovel Knight are the only enemy that cannot be killed, though if they are crawling on a block when it's destroyed they will be temporarily stunned.
Ghosts are a half example. They cannot be killed in the Lich Yard, only stunned, but a special item allows you to kill them in the Hall of Champions.