Lots of it in Mnemosyne: every Big Bad who knows about Rin's immortality prefers to snap her neck first, ask questions later. Goes especially for Sayara.
Also, the ES Members in Kiddy Grade are commonly sent on suicide missions because GOTT can always resurrect them.
In Excel♥Saga, the Great Will of the Macrocosm will commonly resurrect any important character who happens to die. This leaves Lord Il Palazzo free to kill Excel for the slightest irritation. This happens several times in the very first episode and a few more times throughout the series.
The Homunculi of Fullmetal Alchemist get this a lot, as they can instantly regenerate. To be fair, several are eventually killed, but it still counts seeing as one can take three clips of bullets, get up, and ask, "Are you done yet?"
Later really show how damn painful this trope can be. Envy was burned alive several times, and at one point Mustang let his eyes explode. And Sloth was impaled again and again, twice right through his face.
That one guy from Ninja Scroll, the one who turns himself to stone all over... except for his eyes, which is how he gets beaten.
Yakumo Fujii, from 3x3 Eyes. Being unkillable is a lot less fun than you might think, especially when horrible monsters are trying to kill you anyway.
Several characters in Baccano! go to town with this trope, most notably Fermet, who spent a couple hundred years taking advantage of his and Czeslaw's immortality to perform every kind of gruesome "experiment" on poor Czes that he could think of. Then again, since almost everyone in the series is a gangster, a Psycho for Hire, or just plain Ax-Crazy, life is pretty cheap in general, and it's not just the immortal characters who get maimed.
Accordingly, Isaac and Miria avert this, as during the entire anime Isaac was only injured one or two times, and Miria wasn't at all.
Code Geass: C.C. sometimes gets this sort of abuse, such as when Mao decided he was going to "make her compact." At one point, she takes out an opponent by having her mech drag theirs to the bottom of the ocean, and holding them there until they were both crushed completely by the pressure, having her enact this trope on herself — though given that she's a Death Seeker, this makes some sense.
A couple of characters in Naruto are like this. The Akatsuki member Hidan takes sick pleasure in doing horrible painful things to himself in battle after performing a ritual to ensure that his opponent feels the same thing. Hidan is virtually immortal (e.g. getting his head cut off hardly slows him down), but the same cannot be said of his opponents who get trapped by the ritual.
He's paired with Kakuzu specifically for this reason. See Kakuzu has a habit of killing his partners so the Big Bad gave him a partner he couldn't kill.
Bludgeoning Angel Dokuro-chan feels free to beat Sakura to death with her spiked baseball bat any time she suspects him of ecchi thoughts, or indeed, any time she's bored, because she'll just resurrect him for another round immediately anyway.
Love Hina: Keitaro isn't any more durable than is usual for a main character in his genre, but unusually for the genre, other people notice and take advantage of this. Kitsune outright states that lethal force is acceptable against an "immortal" like him.
Throughout the first episode of Kyoukai no Kanata, Mirai repeatedly and brutally attacks Akihito, later giving the explanation that she's literally just using him as target practice because she's unaccustomed to killing youmu. This ultimately turns out to be a subversion since the true reason she's attacking him is to try and kill the extremely dangerous "Beyond the Boundary" youmu that's trapped inside him.
Angel Beats! is full of this, episode 2 probably being the most extreme. As the characters are in maybe-not-quite-purgatory, they'll wake up from any sort of death a few minutes later. The show uses this as an excuse to put the high-schoolers through some truly gruesome deaths. Typically, the males receive far worse onscreen abuse, with the females primarily put in positions where one can simply assume they suffered after the cut to something else. This leads to an interesting dichotomy, where boys will be brutalized outright onscreen far more often, but the girls can be presumed to have suffered far, far worse fates while offscreen. As an example, in the aforementioned episode 2, each of the male members of the SSS is quickly killed by a trap, crushed to death, sliced apart by lasers, etc.; however, Shiina and Tenshi, the two girls to "die", get much harsher deaths: Shiina falls off a massive waterfall and presumably either drowns before resurfacing or goes splat on the rocky ground at the bottom, and Tenshi is dropped into a collapsing, burning factory, and is presumably crushed to death as the explosions brought everything down around her. After which she'd of have to have dug herself out. Ouch.
Hakamada from Aphorism. Used as scapegoat once by his friend to dodge an attack.
Bakemonogatari: The Dying Bird is a type of supernatural creature that reincarnates itself into human form; the resulting human is immortal, and will rapidly regenerate/recover from any injury or illness. The resident specimen, Tsukihi, ends up suffering this trope because of this. For example, Yodzuru and Yotsugi's plan for capturing her involved walking up to her house, ringing the doorbell a few dozen times, and then abruptly blowing off the entire upper half of her body when she finally answered the door.
There's also Araragi himself, who thanks to retaining some powers from having been a vampire, possesses a strong Healing Factor and can survive from fatal injuries, like his heart being crushed into smush. He gets beaten to an inch of his life several times through the series in an exessively gory fashion to show off his determination.
Attack on Titan: Levi will occasionally take advantage of Eren's Healing Factor. He brutally beat him for speaking out in court, and his plan to avoid killing him if he rampages in titan form involves cutting him out, severing all four of his limbs in the process. Annie, Reiner and Bertholt couldn't afford to be gentle in their kidnapping attempts, either.
Several attempts to stop the villain Juggernaut. On one occasion he took a pair of katanas through the eyes. In another battle, all of Juggernaut's flesh and organs were magically incinerated by a powerful demon. Said demon was horrified when Juggernaut's skeleton kept marching toward him. For the most part it takes high-level magic (the above-mentioned swords were magical) to even scratch him, since his power source is a high-level god.
Wolverine has fallen prey to this many times. He is often burned to a crisp, has all of the metal pulled out through his pores by Magneto, and at one point The Punisher shoots him in the crotch with a shotgun, where he then gets his legs sawed on by midgets, and then flattened by a steamroller. There is also an episode in the animated series where Proteus uses his reality altering powers to rip Wolverine in half and then melt him into a puddle (he comes out crying). The other X-Men are also attacked by Proteus, but no one else gets the horrific treatment, even though in this case they may have survived afterward since Proteus's effects go away when he leaves the area.
Likewise, The Hulk is not only Nigh Invulnerable, what damage he DOES take regenerates near-instantly. There's a few strategies that might be instant death, usually involving severe cranial damage, but they're still not sure he'd stay down. He was once caught in a horrid explosion and reduced to a charred skeleton with a few bits of flesh left over. His response? "Give me a minute." Four panels later it was like nothing happened. For the record, it DID hurt, a lot, but it also got him even MORE angry than usual.
Neil Gaiman's The Sandman series features the immortal Cain and Abel, the former frequently murdering the latter over a minor dispute or simply to pass the time.
In the Ultimate Marvel universe, Hawkeye remarks during a fight that the best thing about killing Multiple Man is that there's always more of him.
Deadpool: During one crossover, Bullseye slit Deadpool's throat with a straw because he was talking too much.
Deadpool's sometimes-partner Cable has been known to telekinetically blow up his brain to get him to shut up for an hour or so.
DC Comics character Resurrection Man gets this a lot, naturally. One issue has a confused Batman trying to figure out why the same guy keeps getting murdered by Gotham City criminals. A crossover with Hitman sees Hitman repeatedly shooting him over and over until he gets a useful power. In the 853rd century, even Resurrection Man himself gets in on the act, wearing a gauntlet that lets him commit instant suicide.
Multiman gets this in Last Laugh, where The Joker repeatedly murders him until he gets a power useful in escaping prison. Afterwards, the entire prison gets sucked into a black hole, stranding a number of people. They eventually escape... by repeatedly murdering Multiman until he gets a power that helps them escape.
Luminosity: The Volturi keep vampires disassembled, in case they can ever find a way to bring them to their side. Sort of like freezing someone, except they're in terrible pain. And alone. For years.
Films — Animated
Wreck-It Ralph: As long as a video game character is in their own game, they will regenerate if killed. That's how villains can be defeated day after day. However, if they're are in another game, the character is Killed Off for Real.
Films — Live-Action
In Pirates of the Caribbean: Dead Man's Chest, Captain Jack Sparrow has developed a habit of shooting the undead monkey whenever he is angry.
Men In Black has Jeebs, who can regrow his head. Knowing this, the Mi B like to blow his head off any time they are angry, or if they want something from him, or even if they just feel like it. However, he still does feel excruciating levels of pain when they do it.
In Richard K. Morgan's Takeshi Kovacs series, everybody is implanted from birth with a "cortical stack" that records their personality in case of death. The hero occasionally kills people and steals said stack for later interrogation.
Accelerando: Taken to extremes in the last chapter of Charles Stross' novel. Children, free to take backups of their personality, play war with real weapons. Additionally, they keep software copies running at faster-than-real-time to grow up and watch over them.
Threnody in Xanth often cuts off bits of her husband Jordan, such as his tongue. This is not considered a big deal because his talent is incredible healing.
Gilbert Gosseyn in A.E. van Vogt's The World of Null-A can be killed, and then he just wakes up in a new Gilbert body with all his memories.
Used and subverted in Kiln People by David Brin, in which people download their personalities into short-lived clay golems which they use for work and pleasure. While these golems are regarded as expendable, no-one risks their real self any more, and for someone to suffer even minor injury is quite a scandal.
Simon R. Green's novel Hellworld features the protagonists being dropped onto a planet to determine its potential for colonization. They find the planet apparently devoid of most animal life, with large pools of what can be described as greyish, primordial goo. Then, they discover that the advanced alien race that lived there constructed a machine that made them immortal and protean, able to take on any shape they willed and unable to die. The psychic member of the group discovers that the aliens had eventually become violent sociopaths, fighting endlessly until the machine grew bored and turned them into said goo. To make matters worse, that machine? It's still around. And insane. And starting to affect mutations within our heroes.
In a story Distant Rainbow by Strugatski Brothers, Camillo is a cyborg whose machine part (and that includes brain) is virtually indestructible (can sustain nukes without any damage) and can regenerate the living part of his body even from nothing, using raw materials. So Camillo dies thrice in the course of just one day and is going to die a fourth time when the Wave kills everybody and he will regenerate afterwards, too.
Played increasingly for comedy, to the point where Angel will walk around with a sword through his chest, looking only slightly miffed.
To the point where Spike doesn't bother aiming around Angel to hit a target; Spike just stabs right through him. In all fairness, that was Spike...
Spike: Heat of battle. Wasn't time.
Angel: You just like stabbing me.
Spike: I'm shocked that you'd say that! I much prefer hitting you with blunt instruments.
Cylons in Battlestar Galactica (Reimagined) would occasionally shoot each other without batting an eye if it were expedient, since they could download into new bodies. The horrifying aspect is played up on occasion, such as when a Cavil mentions being too impatient to bleed to death after an ambush, and so has to cut his carotid open with an empty shell casing. Later episodes also feature the prospect of 'death as a learning experience' and the major trauma caused after someone is killed in an especially gruesome way and essentially suffers the worst PTSD ever.
Buffy the Vampire Slayer: In the first season, Darla at one point shot Angel. She told Buffy, "Don't worry, guns can't kill vampires. Hurts like hell, though."
Leo from Charmed, who can reassemble himself if his body is destroyed. The sisters have occasionally used him for target practice (with and without his consent), and a throwaway gag indicates that Piper tends to make him explode when she's mad.
The crew on Farscape once ganged up on Pilot and forcibly amputated one of his arms, so they could sell it to a scientist. They rationalized this action because Pilot's species can regrow lost limbs. Another member of his species on a different ship was actually used as a replenishable food source for this reason.
Heroes has Claire Benett, the immortal regenerating cheerleader. Guess who from the cast is suffering deadly injuries on a fairly regular basis?
The writers of Misfits seem to gain some kind of sadistic pleasure out of killing the immortal character Nathan Young week after week in ways so gory and painful that it quickly becomes hilarious. The fact that he's a total Jerk Ass might have something to do with it.
The immortal heroine in Painkiller Jane was repeatedly shot by her friends for very little reason. Examples include being in the way, to convince someone else they were bad-ass or just for a cheap trick. Incidentally she was called "Painkiller Jane" because she had to eat a lot of them. Because she was repeatedly shot. By her friends.
She also shot herself plenty of times, like to convince a mind-altering Neuro that she reversed his nightmare-causing powers on him by shooting herself in the hand and having him watch the wound close.
She can die given sufficient damage. In one episode, her body is pulverized by a claymore mine. Luckily, this episode has a "Groundhog Day" Loop, and she is fine in the next cycle.
Sanctuary: Nikola Tesla is the occasional Butt Monkey, since, being a vampire, he can't die (at least until he is turned back into a human, sort of). He has been stabbed, electrocuted, having Jack the Ripper's fist punched through his chest, sliced with claws, dropped from a high-rise, etc. And he's still as cheerful and annoying as ever, especially since he lacks the any of the traditional vampire weaknesses (he walks in the sunlight, can eat and drink, does not require blood, can survive a stab through the heart).
In Torchwood, Captain Jack Harkness becomes an absolute damage-magnet for the first series-and-a-half, after which other characters start eating bullets. The Master points this trope out right after he zaps Jack with a laser screwdriver. "And the good thing is, he's not dead for long. I get to kill him again!" Then Jack gets buried alive for 2000 years, constantly suffocating and reviving, somehow without going insane.
Baldur, the Norse god of beauty, had a prophetic dream of his own death. His mother, the goddess Frigg, responded by making everything on Earth vow never to harm Baldur—effectively making him Nigh Invulnerable. The other gods react to this, in jolly Norse God fashion, by making a game of hurling things at him, all of which harmlessly bounce off. (Unfortunately for Baldur, his mother neglected to bother with getting the lowly mistletoe to take the promise, so Loki, the JerkassTrickster, made an arrow out of mistletoe and tricked Baldur's blind twin brother Hod into shooting Baldur with it, killing him dead.)
Another (completely different, by the way) version of the myth simply has Baldr as the rival of Hod (who is mortal) and already resistant to anything but a certain sword, whose name is Mistletoe.
In a Shadowrun monster-book, attached in-character comments by shadowrunners include remarks by someone the SPCA would probably burn at the stake. He claims to make a living by trapping Weres (sapient, regenerating animals which can take on human form) and repeatedly skinning them, then selling the pelts. Live-butchering a type of giant regenerating shark for meat was also mentioned.
In Brazilian RPG setting Tormenta, the city of Triunphus is a place where people get Back from the Dead a few times after being killed. The net result? Death penalty for even mundane things!
There are sidequests in Planescape: Torment that take advantage of this. The Nameless One can break his own neck to win arguments or let a woman pay for the opportunity to stab him, among other things.
And then there's the Practical Incarnation's 'tomb', an elaborate deathtrap for his enemies where the only way to navigate it is to die. Repeatedly.
Mokou actually endorses this on herself as a way to toughen up her body against attacks, in Inaba of the Moon and Inaba of the earth. Amusingly, this is with Reisen, probably the only person in the series who wouldn't be looking for an excuse to get in a fight.
This trope is why fairies in Touhou are treated as Cannon Fodder; they just regenerate offscreen after being blown away. In the games where she's playable, it's implied that Cirno only gets a Game Over because she gets bored and/or gives up.
In Phantasmagoria of Flower View, Shikieiki warns Cirno that if she continues to become stronger and more intelligent, she will surpass what fairies are meant to have and become a youkai... a mortal youkai.
There is also Raziel from the Legacy of Kain series. Managed to get yourself killed? No worries, you just get sent to the spectral realm where sucking on souls floating there gets you back to the land of the living. Managed to somehow get yourself killed in the spectral realm? No problem, you just get sent to an earlier check point in the spectral realm where there are lots of free floating souls to eat. There is no way to get a game over because you died.
Inverted in Solatorobo, where Red is upset at the thought of having to leave the immortal Paladin Elh inside Lemures while he takes on Tartaros. She points out to him that she is technically immortal, and he notes that somehow, that doesn't make him feel any better about it. Considering Baion wiped out the rest of the Paladins and her form of immortality is just "never ages but can be killed", he's right to worry.
EVE Online. The core sci-fi concept of the game is that you're an immortal spaceship-flying cyborg who will, at worst, suffer some minor memory loss from being vaporized. This results in the death penalty being the first resort for even minor infractions and schemes, and is the in-universe explanation for pilots trying to kill each other at random in PvP.
The Materials of the Magical Girl Lyrical Nanoha A's Portable games are Humanoid Abominations who could survive getting reduced to nothing since they could just reconstruct their physical bodies over a period of time. Despite being as strong as the heroes, they've been killed several times in the games they appeared in, especially in the first game where the Material were killed multiple times over the course of one night by all the playable characters, including Technical Pacifist Nanoha.
Ran from Bob and George, who can be killed by a sneeze, but will have a new copy teleport in with memories intact. He is a good guy. The good guys kill him for practical reasons, such as needing multiple copies of his Cossack Buster, or just needing bodies. Or because they think it's funny. He's more annoyed by this than anything else. Apparently it's far more practical to go through with this than simply giving him a body that is durable.
In one Muertitos arc showing Death's brief career as a cartoon hero, Death fights a number of villains, including Multiple Chin, a chinese acrobat with multiplying powers — who is actually a hero who's been brainwashed to work for the bad guys. Death slaughters Chins with wild abandon even over the protests of his sidekick, claiming that she's fine as long as there's at least one left. Then he realizes he's killed them all without thinking. The Commissioner even makes a brief mention of this at the end.
Zandar from Zandar's Saga, practically can't die as a punishment from the devil, having to regenerate from stabbing, drowning and even hanged to death.
Subverted in Sorcery 101; Danny casually shoots Brad in the heart to demonstrate how Werewolves can't be killed by normal bullets. Turns out that you can cure a werewolf, but it reverts all the injuries they've suffered. So now Brad can never become human without getting an instantly fatal gaping chest wound. D'oh! To be fair to Danny, Brad already had all sorts of injuries that he couldn't survive that weren't Danny's fault... except for the first one
In Starslip, the Quels' policy for Cyte attacks to to let the Cyte kill as many as they want until they leave.
Also, Protocol Officer Quine is essentially meant to be the face of the Paradigm wherever it goes, no matter how unhappy the locals are to see them, so his memory is constantly uploaded to the ship so that, in the event of his death, they can be downloaded into a clone so that he can get back to being an annoying busybody.
One arc features an excellent example of this trope: terrorists have hijacked the Paradigm and trapped the crew in a space station. Solution? Kill Quine so that he resurrects back in the ship and wait for him to rescue the crew.
Quine 'dies' many times in his attempts, and uses his previous bodies as props to trick the terrorists.
Obligatory Homestuck example: Immediately upon learning about the God Tier, John hatches a bunch of plots that rely on abusing his new immortality... then learns (thankfully before enacting any) that they all fulfill the terms to nullify his immortality.
When in Ansem Retort has Riku being killed, mortally wounded, attacked by evil Sora clones, pranked by Zexion, poisoned with mustard gas, thrown in a volcano, and/or getting his face eaten by a monkey not been played for laughs?
A minor Running Gag in Schlock Mercenary involves the abuse of fabber and shipyard robots, whose memories and personalities are regularly backed up and downloaded into new bodies if they are damaged or destroyed. Precisely because these robots tend to be on the receiving end when stranded ship crews need to vent their frustration when their ships are in drydock.
Jix: Kelelder's head was blown up at the start of his first battle with Jix, it grew back and he started fighting again, and he has been teleported into the sun twice. Heleatra once demonstrated her immortality by stabbing herself in the stomach, and has been filled with tranquilizer darts, vivisected, and shot in the head with a raygun.
Starscream from Transformers Animated gets killed a lot. Transformers in general tend to get this treatment. Being eons old war machines, they are very hard to kill. Waspinator, being nigh unkillable even by Transformer standards, gets it even worse.
Lampshaded, inverted, and played both for laughs and drama in South Park with the super power of Mysterion. Being Kenny, he has died a thousand times, but wakes up back in his own bed every morning with nobody remembering that he died. At one point he gets so pissed off that nobody believes him that he can not die while he has to suffer through the pains of all kinds of horrible deaths on a regular basis and shoots himself in the head to prove it, but two minutes later everyone has forgotten. He later uses his ability to escape from R'yleh by throwing himself into a chasm to awaken back in his own bed and searching a way to save his friends, who are still trapped there. After everything is said and done, Mysterion mention that he's tired and just wants to go to bed, and shoots himself in the head again as a shortcut.
Agent K of Men In Black has no compunctions about blowing the head off of the immortal alien informant Jeebs as part of his regular interrogation technique. Jeebs, after regenerating his head, usually complains about how much it stings before relenting the requested information.
There're also other Butt Monkey treatments for Jeebs; he also gets stomped into a puddle by a giant alien and ripped in half by a couple of teleporter guns.
In the animated spoof film Igor, the titular character previously succeeded in reanimating and gifting a rabbit named Scamper with immortality. One problem: Scamper has a death-wish and takes every opportunity to test the limits of his regeneration.