I've been playing Batman Arkham City, very cool game. I don't generally read comic books but Batman I've always liked, at least when he's done right. Emerging long enough from the shadows to swallow someone up, leaving a scared criminal fearfully gazing into the darkness. Though B:AC doesn't always play it right, way too many instances of having to enter through the front door. Anyways, this was my first encounter with this villain in the above title, who like many of them had some kind of silly theme to them, this one being named after a nursery rhyme.http://en.wikipedia.org/wiki/Solomon_Grundyhttp://en.wikipedia.org/wiki/Solomon_Grundy_(comics)
At first glance, he appears to be some kind of Mary Stu. I mean a villain who can never be killed? Pssch. But, I feel that the tradeoff he takes for his "immortality" is severe enough as to render him interesting. Every time he is ressed, he loses his memories, his identity and as a consequense part of his mind.
So to make a tabletop villain out of that... Let's say we start with a normal mastermind kind of villain, someone who has a plan, but is still very physically weak. Nevermind the lore of why the whole ressing thing is possible in the first place, there's hundreds of ways to justify that.
The first encounter would just be a mere nuisance, another day at the grind basicly in terms of combat, but hopefully pulled off with enough flair to make them memorable. This portion could be dragged out a bit, a recurring villain would of course have more history and merit more than a shrug, but the fact that they're the kind of villain that keeps returning shouldn't be apparent at this point, so avoid all plot armor, if they kill him/her, (s)he's dead.
The second encounter then, the first resurrection. A flesh golem would make a very easy conversion. Just add some speech and a bit more strategy than merely slam slam slam. At this point, start hinting at the loss of memories, that the villain isn't all there anymore. For now it's just a tragic Frankenstein, and they probably won't think that once the villain is down that (s)he would get up anymore.
The third encounter. This is where they'll either start to worry or just get plain annoyed, or both. Remember to really beef up the villain with each encounter, really push the recommended limits. At this point, our Solomon might not even remember our band of stalwart adventurers. And maybe another recurring villain is using them as their ultimate weapon or some such. Now depending on just what keeps the character immortal, this could drag on for as long as the heroes don't completely destroy their body. Again, I wouldn't take it too far, unless it would hint at the greater story of the game. Since our Solomon would significantly beef up with each encounter, it could eventually reach dragon or god territory, but at the same time, killing the same foe over and over isn't all that fun either, so it would have to be varied somehow. At least one new attack per itteration and a new and interesting arena each time. The upside(?) though is that you would start out fighting an intelligent being but in the end it would have become a near unstoppable beast of pure force.
The opposite would also be an interesting thought. A beast that would slowly get smarter.