I once did an immortal character, DM friend of mine needed a fleshed-out, semi autonomous pseudo-NPC, sort of a supporting character for a campaign he was running for some newer players.
Physically, he could be destroyed, had exceptional but not supernatural pain tolerance, and could regenerate from anything that might happen to him, though it may take a while. He'd been alive for a very long time, and though he didn't have the gibbering incompetence that extremely aged characters sometimes get, he did have an issue with memories: after a while, no matter what he does, they just fade away.
Now, what with everything from his past slowly being destroyed, all he has left of the vast majority of his past is his memories. And, so he feels, without his past, he wouldn't even be himself, a fate worse than death in his eyes. Hence his bargain.
Essentially, he went to a demon that was closely connected to why he was afflicted with immortality in the first place, and made a deal: this demon would save his memories at the moment they faded from his mind, making them freely accessible at any time, as if he'd never forgotten them. The catch: periodically, he would need to kill someone, sacrifice them to this demon, and then perform a ritual that would erase all memories and records of the sacrificed, except that he would remember everything about them in perfect detail.
This leads to a situation where he routinely commits what he believes is the worst thing you can do to someone in order to keep that same thing from happening to him. Also, he's lived for so long that many of the people he murders are probably his descendants, but that's a more minor thing.