Bribes seem too easy to me, especially with rebels. I used to just resist doing them, figuring it was too unfair. But lately I've been trying some house rules to spice things up:

1. The leader of the rebel army always gets the provincial title. It only makes sense that the guy I had to bribe ought to get the title. Even if he has horrible stats, he's the leader.

2. I can replace him only by assassination or inquisition -- no wimpy stripping him of his titles. If he's a problem, I have to kill him to get rid of him. Strikes me as more medieval.

Otherwise, it's just too easy to bribe a rebel army, pick out the best leader in the deck and shuffle the old guy back into the middle of the stack. It's still too easy to bribe, but this way at least there are some more potential consequences.