I haven't read everything posted here yet, but I will, this seems like a great thread and something everyone should keep in mind when writing I think their character darker character arcs.
Jamie lannister's arc is one of my favourites, certainly in the series, but also in any book I can think of off the top of my head, I like nothing more than a redemption arc it seems (Spike, in the buffy series fits here perfectly as well) but you have to be careful, as others have stated, there might be a limit to how far you can push the majority of your audience with this (spike and Jamie, kinda put me away from this group though
). I think all characters need some kind of redeeming quality, especially if they are out and out baddies.
I just finished Wuthering Heights today, I enjoyed it for the most part. What stopped me enjoying it completely... (do i need a spoiler alert for a book this old? Half unrelated note, Anna Karennina's ending was spoiled for me in a 'seven basic plots' book, not two weeks ago
)... was the fact that I didn't find a single likeable quality in Heathcliff, not one, in a character perfect for a redemption arc. For me he was a plain black and white baddie, and it did ruin the story a little, in my opinion. I couldn't see why the characters around him listened to him, believed him, liked him, trusted him etc. while all of this can be explained away through 'reasons' I would have liked some more good in him.
That is pretty much my only requirement to buy into your redemption arc, give them something that is worth redeeming, or give them a reason to want to redeem themselves, even if they don't quite understand why they protected the innocent child or saved a picture of a random old couple from burning in the house they just set fire to, for example.