Firstly, KC will make any player cry foul at some point. Remember that, assuming you are a similarly skilled player, you'll be doling out the pain with KC your fair share of the time too. This is going to be true about any power card.
Possession however is a bit different only because I believe it requires a lot more strategy than KC and is quite often misplayed. I forget where I read it (perhaps it was theory's frontpage article on Possession), but the advice that says the key to a good Possession deck is to 'have Possession and a pile of crap (or premature VP buying, unequivocal attacks, Bishops, Monuments, etc.)' really holds true.
How Possession should really warp a game is to disincentivize each player from having a potent deck. The thing with Possession is that it's an absurdly expensive card. If one is to invest in it, it better yield significant returns. The mistake I see most players make is that they play Possession games like any other game and just cross their fingers and hope their opponents don't pull off some monster Possession turns not realizing that there's a lot they can do.
If both players go for Possessions, the resultant game should be a stalemate involving many of the aforementioned 'pile of crap' tactics. This is actually exactly what should happen if you have two equally matched players playing the same strategy near optimally.
If one player goes for Possession, then I feel the game is decided by that narrow window of the first Province and Possession buys. If the Possessor successfully nabs some Provinces with the non-Possessor's deck, he/she builds a lead puts his/her opponent in the uncomfortable spot of keeping his/her deck powered and attractively possessible. However, if the non-Possessor builds the lead first it's possible to begin greening his/her deck in such a way as to have already secured enough Provinces at the peak of his/her buying power and leave the Possessor with the scraps of his/her now somewhat green deck.
This of course is a generalization and shuffle-luck will undoubtedly be able to change how some of the narrative plays out, but I believe by understanding this general case some less experienced players may finally get over the hump of understanding how to play Possession games rather than simply complain about it.