[Fate]

Movement is always before battles UNLESS they happen to catch each other. Big armies (like the manual says) are the only ones with a realistic chance of accomplishing this, but yes, one guy could stop your invasion that way (don't count on it for defense). Then there is a 50/50 chance between the two territories.

There are a variety of ways you can stop an invading army. (1) out guess it and engage the army in battle. (2) surround the invading army with your own armies (if you significantly outnumber them). Or (3) raise PD around them, hopefully wearing them down. If you are dealing with some super-army which can beat PD without a scratch, then you need to use armies (most armies will have some weakness, the exploitation of which will eventually bring them down).

A final possibility is flooding the countryside with assassins/seducers or calling assassination spells all over the place. Assassinations take place before movement, so offing the commander might stop the army and allow you to kill it.

However, as in many games, a good deal of strategy involves fighting on enemy territory and trashing their land so they can't -or won't- trash yours (LA R'lyeh and Ermor not included).