Part of it comes from the way they portray Kane. Like The Undertaker (and a few others that never really stuck or didn't last), he's portrayed as something of a supernatural being. So even though he's openly admitted to being a vicious sadist, he comes off as more of a force of nature — it's just what he does. Compare to the usual heel who's just a disrespectful, selfish, greedy, cowardly individual in it only for themselves, this makes Kane seem more likable. It also has something to do with the fact that, unlike most heels (as previously stated), Kane is very rarely portrayed acting in a way that would be seen as cowardly. He'll go face to face with an equally matched enemy (every battle royal the man's ever been in has had him and the other biggest man lay everyone out, face off, and go at it), or even a group of opponents. Add to that the fact that he's had enough Pet the Dog and Kick the Son of a Bitch moments over his career, he's fairly hard to hate, even at his worst.
It doesn't help that, even when he's a heel nowadays, the fans still cheer for him.
It also helps that the guy portraying Kane, Glen Jacobs, is a decent performer, hard worker, loyal company man, and really nice guy in real life.
Mick Foley skirted the line of anti-villain as Cactus Jack during his "anti-hardcore" gimmick in ECW. Though he was technically the villain, his motivations were that he wished to "save" Tommy Dreamer from the fans who demanded he risk his body night after night to entertain them. Specifically, Foley mentioned that nobody cared how much he had personally risked his body for wrestling (including a ripped-off ear) and thus had given up on trying to pacify the rabid ECW fans. Hence, Foley would try to convince Dreamer to go to WCW where it was supposedly safer and more lucrative. Nevertheless, he managed to keep heat as a heel by A.) dropping his movelist down to a headlock, thus pissing off all the hardcore-hungry fans and B.) constantly praising the mortal enemy of ECW, WCW's Eric Bischoff.
CM Punk, as a heel, portrays a man legitimately concerned about the well-being of mankind. The idea is that he is trying to save us all from our addictions that we are supposedly a slave to. Of course, he can let his forceful nature get the best of him and try to beat sense into people who don't listen to him. This was shown best in his feud with Jeff Hardy, saying Jeff should stop acting so recklessly and quit making excuses for his behavior. In fact, it worked so well that some people felt Punk was the real face in all of this.
In the AWA, Nick Bockwinkel was so eloquent and well spoken that even though he referred to fans as "cretinous humanoids", fans could always plainly see his side of the story. How could defending the title in Japan on short notice against Jumbo Tsuruta under a different rule-set be considered fair? Why would Rick Martel get a title-shot before his rematch? He seldom took things personally with his opponents and always conducted himself with an air of dignity and nobility. He would also periodically feud with more vicious heels like Sheik Adnan Al-Kaissie.