chris: I assume you have units that were lost in the void? If so, they were fighting enemies in the void BEFORE the patch, but now you can see.
rdonj: That is WAD. Two armies moving to the other's territories have a cahcen of missing each other. If they do, they fight in the territories they were moving to. If they don't miss (in general, larger armies should miss less) then there is a 50% chance that they fight in either territory.
If you are attacked from multiple directions and your army manages to leave it's territory it will not defend against the attackers, so that is another way to miss fighting the enemy.
Just to be clear - the AI has nothing to do with this. Any player moving towards you might just pass by instead.