I just thought of an example for Tyrion:
Some people have complained that the d20 and 4e mechanics make it too easy for characters to make Diplomacy checks that seem unrealistic (that is the purpose of this thread, after all). In fact, logically it would seem impossible to move an NPC from hostile to friendly, no matter what a player's roll was.
However, isn't this similar what Tyrion does (who has no magical abilities what-so-ever) when he returns to Winterfell coming back from the wall and is greeted with much hostility from Rob Stark. I'm not sure he moves him all the way from hostile to friendly, but from what I remember it's pretty close.
Some of my other favorite examples from that same book of his Diplomacy skills is when he is in the Eyrie (both in sky cells with the guard and when he "confesses"), and also when he convinces the wild men not to kill him on his way out of the vale.
These examples are fresh on my mind because of the TV adaption, but I've read the entire series, and there are many, many more examples.