"Ask not elves for counsel, for they will tell you no and yes."
My particular take is that role-playing encounters that do NOT involve avoiding a fight should be given CR's in a fashion similar to traps. They share many of the same mechanics: one or two rolls by a PC decides whether or not he takes a hunk of damage (perhaps "social damage"). Along those lines, I'd put the CR of a role-playing enounter at about (main skill DC - 18). This is assuming a level 1 character can reasonably get about a +8 in the key skill if he worked at it (better results are possible with racial mods and Skill Focus, of course). Thus, a CR 1 encounter would be one where a skilled level 1 character can't quite get away with taking 10 to succeed at the key skills.
The previous assumes one actually uses skill rolls in role-playing situations. I recommend doing so, because the reactions of the NPC's should be based on the character's Charisma, not the player's Charisma.
However, if the PC's negotiates with potential foes in such a way that (1) avoids a fight, and (2) provides a result similar to winning that fight, I would award XP equal to the actual strength of the monsters. If they avoid a fight, but don't particularly solve the problem the potential foes would have posed, I'd give half XP at most (less if the PC's didn't give it a good effort).
For example, avoiding an encounter with animals should probably yield full XP because the animals will probably not go out of their way to trouble anyone else. Letting a group of bandits walk away without a fight means they are still a possible source of trouble to the PC's, so they are not yet entitled to a full XP award (half, or less if the PC's were actually sent to STOP the bandits).