The odds are not rigged. It is just that 99.8% odds means that you will still fail 2 out of 1000. And those are the two that you will remember. In a single game of Civ4 you will be attacking more than 1000 times.
Also, one thing to note is that the combat odds display is faulty for any attacks that is not from the square you are in. For example, if you have a chariot about to attack a bear on a hill two squares away, the displayed odds might be 99.8%. However, to attack the bear, you actually have to move to the square in between and from that square, you have to cross a river to attack it. The displayed odds does NOT take into account that river crossing which reduces your strength by 25%. This is true of any other feature that might affect your combat odds from the attacking square. The displayed odds are for the square you are in versus the bear. Move to the square next to the bear, and your odds will suddenly change for the worse (river crossingis finally taken into account). So, your 99.8% odds suddenly flubs to 60% and you get swatted.