It surprises me that there is nothing to find about these two messages either on the forum or the wiki, since they are very very common and nobody seems to know what they're actually telling us.
The exact wording can be found in this example: http://www.ageod-forum.com/showthread.php?34340-Why-did-this-battle-happen&p=303845&viewfull=1#post303845
There is some kind of evade-check and an engagement-check, and both come with probabilities in %. Does anyone have a clue why/when these checks are made, what they're for and how the probabilities are calculated?
I can only guess what "successfully evaded" means: Perhaps it refers to a successfull retreat before the first round of combat (in which case the battle-screen doesn't pop up)? And the chance of success was the retreat-check-difficulty of that test?