This is the whole premise of the fourth season of Yu-Gi-Oh! and the second season of Yu-Gi-Oh! GX, the "deal" being gain unstoppable dueling skill, power, and strength in exchange for your free will/soul and vow of service to the leader of the cult. In fact, GX developed quite a fondness for this trope with...
Manjyome, with Saiou. (Who trusts a guy who approaches you in the forest in the dead of night, knows way too much about you, and makes it clear that he has inhuman powers?)
Kaiser, with Saruyama. Once Hell Kaiser has the skill and victories he wants, he kicks Saruyama to the curb (literally booting him out of his limo) and goes off on his own. Saruyama is never seen again.
Professor Cobra, with demonic Judai-obsessed Duel Monster Yubel in Season 3. Though all Cobra really wanted was his son back, not unstoppable dueling skill or anything.
Amon Garam & Martin Kanou, both of whom gained a portion of Yubel's power to achieve their goals. Martin's being to have friends (so, we get the Martin Zombie Empire) and Amon to be able to kill those he loved without remorse (he got that, too, then dropped Yubel like a hot rock).
Borderline Lampshaded in a Season 2 Filler episode, where the "devil" is the actual "Grim Reaper"; a duelist promises his soul in exchange for his very difficult-to-pull-off OTK combo working. In a Twist Ending, he ultimately rejects the deal, and his strategy ends up working anyway.
Thief King's teaming up with Zorc.
In Yu-Gi-Oh! ZEXAL, this may or may not be an important part of the plot. In the beginning of the series, Yuma makes a deal with a demonic entity called simply "the Door". It says "Whoever opens this door will obtain a new power, but in exchange will lose what they appreciate the most." Yuma accepts this offer, and later meets Astral, gaining the ability to fight and control the Numbers. The Door appears later, giving Yuma the Zexal Power and this time saying that it will cost Yuma his most precious belonging. Still later, the Door tests Yuma, forcing him to battle a demon called the Shadow Giant; after Yuma is victorious, Astral gains another useful ability. It is not yet known what this being will eventually demand from Yuma, but clearly, this will remain a constant part of his career for at least the time being.
The anime Hell Girl revolves around a demonic young girl who offers people the chance to instantly send one of their enemies to Hell — although the price for this "service" is that the sender's own soul will also be sent to Hell after their death.
The creation of the flame man in Mermaid Melody Pichi Pichi Pitch turned out to be from such a deal. He was originally a human that had fallen in love with a weak Panthalassa that had managed to escape the seal. Fuku-chan offered him a way to save his daughter, who had inherited the weakness in body after her mother died. Michal became Michel's mana battery, and her father became the flame pillar, the apparent authority actually ruled by Fuku.
Witsarnemitea in the anime/Visual NovelUtawarerumonoloves to grant 'wishes', particularly in the mysterious backstory. For instance, DO YOU WANT A STRONGER BODY? DO YOU WANT TO LIVE FOREVER? ENJOY BEING TURNED INTO A RED JELLY, ASSHOLE. DO YOU WANT TO LEARN MORE ABOUT ME, PHILOSOPHER? HOW ABOUT I TAKE COMPLETE CONTROL OVER YOUR BODY FOR THE REST OF ETERNITY, LOL. Sometimes you have to swear your entire being away in a contract in order to get help, though.
Rather subverted by his sane half though, as Eruru makes the 'ALL YOUR BEING IS MINE' pledge in order to save her sister, but is never really held to it aside from being his companion. For a cosmic thing that offers wishes in exchange for their being, it's like he just uses that as an excuse to have friends. He even completely nullifies her debt to him once he figures out his identity, with no payment or repercussions. His other side, on the other hand...
This is sometimes the way Yuuko does her work in Xxx HO Li C. She plays the Mephisto straight, where she grants people any wish they desire as long as they can pay something of equal value to the wish (She even refers to this price as a "soul" in one occasion, tough only to mess with Watanuki). For example, when a woman wanted to have a cursed picture that showed her murdering her friend locked away, Yuko's price was that the woman could never have her picture taken or recorded again - dooming her to a life of exile due to the abundance of security cameras around.
It isn't always the case, though. Although sometimes the results of wishes are quite nasty, sometimes the Faustian parts simply learn a lesson the hard way and move on with their lives, and there are even quite a lot of times where there are no tricks whatsoever and the whole thing is treated as a simple transsaction where both parts get what they want and happily go their own ways. In one case, an internet addict asked for Yuuko to help her break her habit - Yuuko asked for an ordinary baby's chair, then destroyed her computer. When called on this, Yuuko says that all she did was destroy her computer - the addict can always get a new one. Yuuko hopes that seeing her computer destroyed would cause her to rethink her addiction and get help. And since destroying a computer isn't exactly all that hard to do, she didn't have to pay that high a price.
Also, in keeping with the CLAMP mantra that the dead cannot be revived, Yuko cannot bring the dead back to life because no payment exists to make such a wish "fair".
Incidentally it turns out Yuuko herself is the prime example of what happens if someone tries to bring back someone to life, as an accidental wish froze her in a state that is neither death nor true life. The universe ends up screwed over because of one person's attempt at truly resurrecting her and it still doesn't work.
Tsubasa Reservoir Chronicle has a more typical example- Syaoran made a deal with Yuko's evil counterpart, Fei Wong Reed (aka the "person" mentioned above), to reverse time in order to save someone, for the low, low price of allowing Ass-chin to clone him. Oh, and borking up the entire space-time continuum in the process.
Fai makes a similar deal with Reed: Reed promises to bring his twin brother back to life if Fai works for him as a sleeper agent. Reed intends to use Fai to defeat Syaoran, but Sakura interferes and is killed instead.
The pacts between humans and Shinigami on Death Note work in this manner, as Death Note users gain the power to kill anyone using the book if they know their name and face, but is "cursed to live a life of misery and unhappiness". An alternate interpretation of the curse (and an idea independently suggested by Near, who never heard of the curse) is that by using the Death Note, Light had become corrupted.
The shinigami can also offer a second deal, exchanging half of the user's remaining natural lifespan in exchange for Shinigami eyes, allowing the user to know the true name of whomever they look upon, the exact date in time that they will die. The value of the second deal for the Shinigami isn't immediately apparent, but if a Shinigami lost their only note the deal could become the only way for them to extend their lifespan.
In Fullmetal Alchemist, Ling agrees to let Greed possess him, effectively making him into a humonculus, if it means he'll be that much closer to obtaining a Philosopher's Stone and thus the secret to immortality.
It's not that clear cut. Ling obviously found immortality tempting, but temptation wasn't the only factor in play. "Father" wasn't letting him out of the situation alive, he couldn't do anything to prevent the infusion and if his body "rejected" Greed he'd have turned out like the poor shmucks that failed to become "Wrath" — not pretty. So his choices weren't "take the deal or don't get your wish" but "take the deal (and sorta get your wish), or don't take it and die a horrible painful death", and it's not clear whether he would have done it if it'd been played straight. As it was, he made the best of an otherwise hopeless situation.
Speaking of homunculi, one rather odd example is how Father got his start by betraying all those involved in his utterly monstrous pact with the sole exception of Hohenheim, whom he quite honorably split the loot of the scheme with 50/50, zero strings attached. Since he didn't even ask for it, this gift was its own punishment.
He thinks he's God, although making that true is his aspiration. The beard, the detached arrogant pseudo-benevolence, the 'my son' dropping, the explicit comparisons...the Greed thing, though obviously Father didn't catch that one.
The Gate. It will give you a lot, especially knowledge with which you will have extreme power over the physical world, but it will take 'something of equivalent value' in exchange, and it will make sure that that is the most ironically painful thing it could take. 'Equivalent Exchange' is the catch phrase, but look at that shit-eating grin on Truth Guy: in this universe, God exists, and he is a total dick.
So...Ed is a witch, but it's okay because God and the Devil are one?
Eventually, he finds the back door, too...but he still has to give up a lot.
Kimblee in particular is heavily implied in one particular scene to have made such a deal just to see how the homunculi's games would play out. He ends up rebelling and dying in the end.
Finally, in the 2003 anime version, Lust's shtick was to tempt desperate alchemists into creating the Philosopher's stone with her help. Her backstory contains at least one concrete example of an alchemist she 'inspired' into making the attempt, though her method on the Elrics boiled more down into "make the philosopher's stone or I kill Al."
The Behelits from Berserk are a means to summon the Godhand, four evil demonic gods who offer their bearers the chance to become demonic Apostles (or in the case of those bearing a Crimson Behelit such as Griffith, a new member of the Godhand) in exchange for the sacrifice of those closest to them, who are transported to hell along with the one presented with the deal and marked with the Godhand's Brand of Sacrifice if the bearer should accept, at which point the monsters come out of the woodwork to eat them alive. They're particularly insidious because they are activated by their bearer hitting the Despair Event Horizon, making the bearer particularly receptive to the Godhand's offer.
In Chrono Crusade, demons need a type of spiritual energy called astral energy to use their powers and survive. Typically they use their horns to siphon the energy from their surroundings, but when a demon's horns are broken or for some other reason they need to augment their intake, demons can make a contract with a human. The demon serves the human they make the contract with, in exchange for the demon being able to drain their soul in place of astral energy, shortening the human's lifespan drastically. Most of the demons who make contracts in the series follow the typical archetype of being tricksters, but the title character subverts this. He makes a contract with Rosette, a nun, so that he is able to use his powers to help her save his brother, both of whom had befriended him. Throughout the series Chrono questions his decision to make the contract, causing quite a lot of his angstier moments.
Ciel Phantomhive from Black Butler has a literal deal (or contract, as they refer to it) with demon butler Sebastian; he'll help him in all his endeavors, and when Ciel's goals are accomplished, his soul belongs to Sebastian. So far, Ciel has shown nothing but acceptance for this fact, and has yet to show even an inkling of desire to get out of the contract.
In the manga, summoning Sebastian may have had nothing to do with Ciel at all. It's suggested that the cult members sacrificed Ciel to summon Sebastian, and the contract began without Ciel's permission. Hence the reason Sebastian was calling Ciel 'small master' before he even offered Ciel his end of the bargain. In the anime, Ciel actually summons Sebastian willingly for the contract.
The way the flashback scene's set up, there's actually a decent chance the cult members summoned Sebastian for some purpose of their own with Ciel around as an offering, and Sebastian looked around and decided Ciel was the only one worth bothering with. He's a gourmet, after all.
The actual dialogue is something like "what do you say we make a deal? I'll get you out of here and help you get your revenge, if you give me your soul afterward."
Given the kind of life Ciel's led, handing his soul over to Sebastian probably doesn't seem like that much of a loss—his optimism is almost completely excised.
The manga also adds another angle: Sebastian's willingness to fulfill Ciel's every whim isn't just his being Lawful Evil. Nor is it the Ho Yay. Ciel's job as the queen's watchdog, and the trauma it brings him (e.g. Madame Red, the Noah's Arc Circus etc), is tenderizing his soul. Who needs trickery when his prey is ordering him to season it to perfection already?
Lelouch Lamperouge from Code Geass accepts a contract with Mysterious Waif C.C., by which he gains a power to give absolute orders and, in a long run, to change the world in exchange for an unspecified service for her. It turns out, this "unspecified service" is to be Cursed with Awesome/Blessed with Suck by taking C.C.'s place as an undying Geass dispenser. Lelouch even lampshades it towards the end of the first season.
Mao, Mao, Mao.... He had made a contract with C.C. previously, but his out-of-control Geass drove him completely insane, and turned him into a Psychopathic Manchild when C.C. abandoned him. Ultimately, he has to be Mercy Killed by her at the age of seventeen. The sad thing is, that part of the reason he accepted his Geass might have been to have a caretaker in the first place, since at the time he was horrifically young and living on the streets all alone.
Given the Geass is always twinned to the user's deeper desires in some way (sometimes with brutal irony), Mao probably wanted to be able to understand people better so he could get them to care about him, or something like it.
In D.Gray-Man, the Earl of the Millennium promises his victims to bring back to life the person they have lost. He creates a metal skeleton and makes the victim call the name of the one he wants to come back. Then, the skeleton kills the victim and wears his skin, creating a monster, an "akuma".
The soul is enslaved and unable to influence anything, and the form is actually irrelevant, although it seems to have an impact sometimes. Neither survives the first evolution.
But, in the pilot chapter, Allen was a rogue Akuma containing... I think the soul of his sister. Or was he physically a girl and run by the soul of her brother? Can't remember. But an akuma-killing akuma in sibling's skin that was still recognizably Allen Walker.
...in the Naruto pilot Naruto was a fox, Kyuubi's son. Is there a pattern of some kind here?
Yeah. Humans are easier to sell.
In Mahou Sensei Negima!, Big Bad Fate Averruncus offers Negi a deal, but manages to word it in a way that if Negi had accepted it, Negi would have been magically bound to keep his end of the bargain while Fate would not.
In the end of the anime he almost makes one of these to bring Asuna back to life but is stopped before he can go through with it. Actually, this deal seems to contradict demonic nature in this series where they are generally no more than a Punch Clock Villain or in the case of the Demon God in the Kyoto Arc, Too Powerful to Live. And the reason why Asuna is dead is one of these too, in which she agreed to die in her 14th birthday in exchange for not having demons following her everywhere.
Impmon in Digimon Tamers, who was allowed to evolve in exchange for his servitude. Ironically, he's a devil-themed Digimon striking a deal with a Digimon god.
Even more impressive in that you consider his deal is with Caturamon, who shares his English voice with Devimon, Devidramon, and MarineDevimon.
In at least the anime of Slayers, Lina Inverse was offered this during the Gaav/Phibrizo story arc.
Various deals with the Mazoku exist in Slayers canon. One option is the "Pledge of Immortality", where the human becomes immortal and invulnerable as long as they serve the Mazoku. One signatory of such a deal was Halcyform the White, a wizard from Atlas City.
This is essentially The Reveal explaining the plot in Baccano!: the elixir of immortality and the recipe for creating it were given to Maiza by a "demon" he called up. Unusually for the trope, the demon doesn't really make a specific demand in return; his payoff is watching all the chaos that results from the deal; and an infinite amount of intelligence, experiences and 'wisdom' - Received from any immortal who comes to him to die, if they don't want to live any longer, since the method of killing an immortal also gives their memories and information to the killer. Ronnie, the 'demon', is in fact a two-thousand year old homunculus clone of a former self who was also considerably old. Because of this, he is very knowledgeable and relatively omniscient.
In Yami No Matsuei, the Shinigami have to go to the rescue of a boy receives a cornea transplant that results in him taking on the burden of the previous owner's deal with a demon.
This is the violin storyline. Highlights include 'The Devil's Trill' (mentioned below as supposedly having been gotten this way in the first place) and the total failure of the animators to even try to make the bow move approximately with the sounds. Also, Tsuzuki gets possessed. No deals necessary.
In one Urusei Yatsura episode, Ataru Moroboshi manages to fulfill all the complicated conditions to make a pact with a demon COMPLETELY BY ACCIDENT!
After which it becomes painfully obvious that the demon made up a bunch of BS in hopes of duping Ataru into giving up his soul quietly (he doesn't even get his own damn name right). It doesn't work out so well...not only does he fail to get Ataru's soul, he ends up losing all the other souls he's collected! He's last seen trying to convince a woman to trade her soul for a newspaper subscription. Man, even evil incarnate can't catch a break in that town...
Illegal Contractors in Pandora Hearts make deals with "chains" from The Abyss to change their pasts or give them powers in the present. Oz is Alice's Illegal Contractor, although their whole situation is unique. Break made a deal with the Will of the Abyss herself but the exact details have not yet been revealed.
In the final episode, Madoka's solution is to wish to destroy all witches before they exist with her own hands. And she means all witches, past, present and future, in all possible worlds. This causes a loop where Kriemhild Gretchen, Madoka's witch form, is destroyed by Madoka herself. The resulting Reality-Breaking Paradox causes Madoka to cease to exist as a human and become a goddess of hope for Magical Girls. Kyubey was screwed so badly he doesn't remember any of this, and would consider the old world physically impossible.
The one shot manga, Rokuyoku, had Yoshika make a deal with a demonic cat to steal Yukina's traits so that she can get her friend's boyfriend. It doesn't end well.
Akuma na Eros has Satan as a Bastard Boyfriend who agrees to help a school girl named Miu Sakurai, who somehow managed to get her paws on a spellbook and invoked him, to snatch the attention of the resident highschool heart-throb, Amamiya. Yet he demands her virginity as a payment, and is bent on collecting... specially when he sees that Miu not only is very cute-looking, but somehow has a power that can potentially reject his own.
In Dragon Ball Z, during the Buu arc, Vegeta willingly allows Babidi to brainwash him for the power boost that comes with it so he can finally surpass Goku, and it's referred to as Vegeta "selling his soul". However Vegeta's desire to fight Goku allows him to completely ignore all of his new "master"'s orders, and Vegeta dies trying to destroy the monster Babidi unleashed, and it seems either his or Babidi's death released Vegeta from the mind control.
In Kamisama Kiss Tomoe made a deal with a Fallen God to become human in order to live out the rest of his life with the woman he loved, the catch being that the moment she died he died. By making him forget this, the contract was nulled....but once he does...
Count D in Pet Shop of Horrors pretty much is this trope. He will sell you "love, hope and dreams" provided that you keep to the contract. If not... things will go very badly for you. Since this is all a part of his revenge scheme against humanity for eradicating almost his entire species, often it seems as if the humans are set up to fail so they will learn their lesson and then die horribly - but there are also times when human nature surprises him.
In Holyland chapter 147 the Yazuka regular tempts Masaki with Yazuka assistance in dealing with the drug problem if he just joins up. Masaki refuses.
In the 3rd OVA to Fushigi Yuugi, a young girl named Mayo becomes the new Priestess of Suzaku, even though by all logic, she shouldn't be there. She has also become pregnant with the child Miaka had been carrying earlier in the series, and has Miaka's wedding ring. Taka Tamahome goes into the book to gather the other Seishi, summon Suzaku, and set the universe to rights. Mayo enters the Shrine of Suzaku, and the golden statue in there starts talking to her, saying how Taka was really gathering the Seishi to rise up and kill Mayo. Fearing for her life, Mayo asks what she can do to fix this. "Suzaku" tells her to pray for the destruction of Konan, except for herself, Taka, and the baby, promising to keep them safe.