In "The Maiden Without Hands", a miller makes a deal with the devil for "what is standing behind thy mill". He thought it was an apple tree; it was his daughter. She kept herself too pure for the devil to carry off, though, even when the devil orders the miller to cut off her hands. So the miller ended up with the money; but as soon as that happened, the daughter left to seek her fortune. Ironically enough, this may be a Bowdlerised plot; the rest of the plot is commonly found in tales where the heroine lost her hands and left because her father or brother tried to force her to marry him.
In "Bearskin", a soldier makes a Deal With The Devil, who will give him an ever-filled purse, but he must not pray, wash, cut his hair or nails, or change from a bearskin for seven years. He goes about distributing money to the poor, asking them to pray for him. One man he rescues from financial distress promises that he may marry one of his daughters. Only the youngest is willing. He succeeds in fulfilling the devil's terms and cleans up nicely, and the older sisters, reduced to envy, commit suicide. The Devil, pleased at his dumb luck, informs the soldier that he got two souls, not one.
Another fairytale variant: "Rumpelstiltskin". Though considering the number of escape clauses in that deal, Rumpelstiltskin made a less-than-competent Mephistopheles.
A Polish legend tells of the nobleman Twardowski who gained magical powers thanks to such a deal. The clause was that the devil would get Twardowski's soul when Twardowski goes to Rome. Twardowski gleefully stayed away from Italy. The devil eventually captured him when he wandered into a tavern called "Rome".
The Polish poet Adam Mickiewicz had fun with this legend in one of his poems, where Twardowski agrees to give up his soul in exchange for three Impossible Tasks, per the contract. The devil manages to do the first two, but the third one - to spend a year with Twardowski's wife - is too much for him and he runs away.
One story has a wily blacksmith who sells his soul to the Devil in return for the magical power to stick anything to anything (hey, that's useful for a smith). When the Devil sends first his son and then his daughter to collect on the bargain, the smith uses his magic powers to not only stop them but embarrass them until they go away. Then the Devil declares he has to do the job himself, and fails. The smith tells him that if he can just live out is natural life the Devil is jolly welcome to take his soul when that day comes... but when that day comes, the Devil gets so horrified at the idea of having the smith down there, that he screams that the deal is off and tells the smith to get himself packing to Heaven. Which let him in. Apparently, trolling the devil counters engaging in black magic deals.
It is sometimes said that legendary blues guitarist Robert Johnson sold his soul to the devil in exchange for his mastery of the instrument. The location where the meeting supposedly took place, the crossroads of US 49 and US 61 in Clarksdale, MS, is a Mecca of sorts to blues aficionados. The tale is something of a subtrope in its own right, and is referenced in several of these examples. Same rumors exist about other musicians, like Mozart or Paganini.
This has also been repeated in more voodoun terms, since Papa Legba makes crossroads deals as well, though they're not quite as huge a risk, i.e. auto-loss, as the Satan ones.
There are a number of folk tales where people make a deal with the devil (or other supernatural creatures) to build or rebuild some structure in return for a soul, so long as the work is complete before the rooster crows. Of course, there is nothing forbidding the people waking up the rooster five seconds before the work is done.
Witches were said to gain magical powers by making a deal with Satan.
A common theme in Appalachian folklore, the inspiration for the Charlie Daniels Band song quoted at the top of this page.
In Quebec, Canada, a brand of beer is called "La Maudite" meaning "The Damned One." Its name comes from a story where fur traders made a deal with the Devil whereby he would grant them a flying canoe that would allow them to fly to their families for Christmas day. The devil, in exchange, would get all of the traders' souls if they did not return to where they were before the morning after Christmas. Guess what happens?
The picture on the beer is that of the devil sneering at men frantically rowing in a flying canoe as the sun rises in the background.
Dealing with the Sidhe is traditionally known to be along these lines. Fairies are long-lived and wily, giving them both the time and the inclination to get really good at legalese. Getting a fairy to honor the spirit of a deal is like squeezing blood from thin air; depending on how nasty the fae is, even getting them to honor the letter of a deal can be one hell of a trick, if they think they can get away with creatively misinterpreting or even actively ignoring their end of the bargain. As a general rule, if it seems like the Neighbors are playing fair, either your bargain is a case of Be Careful What You Wish For, or you had the upper hand in the deal, which means you're due to be raped by a troll any minute now...
Spoofed in the Chilean folk tale "El roto que engañó al diablo (The poor man who tricked the Devil)", where a young Unlucky Everydude seals one of these deals but, as a proof, he writes it down with his blood on a small paper... writing it such a tricky manner that, every time the Devil came to get him, the "technicalities" wouldn't let him ensnare the man's soul and had to give up.
A similar Irish story, "An Cearrbhach Mac Cába" ("McCabe the Gambler") features the same type of trickery, e.g. he asks to live until a candle burns down... and then blows out the candle so it never goes down. He asks to be allowed to live to say a prayer ... and then delays making the prayer indefinitely. (The villain is Death, not the Devil, but behaves as the stereotypical Devil does.) This is very like the Greek hero Meleager, who was fated to live only until a brand that was in the fire of the fates burned up; his mother stole it, doused it, and kept it safe...until he killed her brothers and one of his brothers, her son, and she burnt it on purpose.
Jack sold his soul to the devil for power and became such a good trickster that he became too much of a headache for the devil to deal with. So when he died, the devil let him go to keep from dealing with him anymore. Heaven rejected the corrupted evil man and wouldn't let him in the gates. He now roams the earth with just his turnip (later, pumpkin) lantern to guide him. Thus, he became Jack of the Lantern, or Jack O' Lantern.