A story I read when I was a kid, was (I believe) On The Devil's Court. I think it even references Faust (edit: thinking back, I think the kid was reading it for school at the time). Basically the kid makes a deal to become an amazing basketball player. Sounds silly, but really engaged me in my youth (perhaps 15-18 years ago?).
Faust has been retold many times. Two more contemporary takes on it are "Temptation" by Vaclav Havel and the humorous "If at Faust You Don't Succeed" by Roger Zelazny.
Just to make you aware of it, there is at least 1 short story (whose name escapes me) in which a man sells his soul...but in a surprise twist, its to an Angel- claiming as an aside that Good uses the tactic as well since it is effective.
Almost forgot this one. A few years back DC Comics had a big crossover titled "Underworld Unleashed." The devil, Neron, offers deals to pretty much everyone in the DC universe and quite a few villians take him up on it.