The other thing - which may or may not be related - is that I've also seen enemy paratroopers move into open ground from a tree, and remain untargetable. It's hard to be certain, because you don't get to see the bonuses which confirm whether they're under cover or not, but I've seen this apparently happen several times now; it happened to me in my most recent GE battle, when the enemy had a single paratrooper left, and he inexplicably left cover and moved to an open hex between two trees for no obvious gain. Except that I still couldn't target him until I moved right next door!
This variant seems to happen at the ends of battles rather than in the first move...
[Edit: I've opened a ticket with in-game support in case they can get any useful data from the battle log.]