45°38'N-13°47'E
Deity
I was having problems like this in C2C but only when attacking in stacks. The problem apparently was some combat mod they added in but forgot to disable (Since it wasn't working properly I guess) that chose the worst possible unit to enter combat when using a stack. A Shock III Archer would fight that Cover II Archer instead of that weakened Stone maceman every time, and melee units would throw themselves against anti-melee units without fail. The game would display 98% odds or whatever, but promptly suicide the unit against something that counters it instead and the combat logs would display something like 8% or 16%.
Given what 45N said, I doubt this is the cause - but it does sound similar
Might be you're just getting very unlucky (It happens) but who knows? I haven't noticed anything different combat-wise yet myself. Still, after you lose a battle like that don't forget to check the combat log. If you lose like three 90%+ odds battles in your favor, check the combat logs to see if they still present those odds prior to the battle. If the game tooltip displays 85% but the combat logs show something like 22% for the same battle, then something might be up.
I've done some test myself and I couldn't find any problems with odds. But I remember in one of the latest changes TB from C2C solved an OOS bug that was causing wrong odds being displayed in single player also. Probably odds shown were wrong before that change. Now they look ok to me anyway.