I actually use assassins very extensively, and usually have a couple of 5 star ones hanging about, killing emmisaries, princessess and religious agents to raise their status, and usually by the early 1200s I will have at least one 6-7 star assassin, whom I use to kill the Pope when he excommunicates me, and any kings who re-emerge with a half dozen stacks of arbalesters, Chivalric men-at-arms and royal knights. The valour is really easy to get up to 5, but then it takes several kings to improve them.