I think I've experienced a similar effect of unexpectedly frequent failures at high success rates. It struck me that this might just possibly be a "feature". Lame excuse, I know, but it's just about conceivable that these failures are not being caused by the dangers which are being taken into account in the % chance of success figure (e.g. bodyguards, alertness of general, number of troops, competence of assassin etc.), but by the presence of an enemy spy with the army/character being targeted. This would introduce a separate element causing failure which is separate to the features of the target, and therefore not taken into account in the % figure.
Of course that could still be a mistake (and given our experiences with this game, that seems quite plausible), but it could also be deliberate and realistic. It's in the very nature of spies that they're undercover - your assassin wouldn't know about them shadowing his target, so he wouldn't factor them in when assessing his own chance of pulling it off. It comes as an unpleasant surprise to him when he sneaks into the target's tent and the nubile young camp concubine in the corner takes off her wig and reveals herself to actually be Jamesus Bondus. Just looking at the guards etc. that he knew about, he calculated 95% chance of success, but the spy he couldn't foresee reduces this.