He is flying (look the log below), however instead of seeing the message of it I see the message of 'armor protection'. Looks like this skill checks before the flying check.

Also it seems it procs a bit too often, I am a thief, and I assume aim/precious aim/opportunity strike should help against armored foes, however ->

*snipping log*

1 - A NUMBER of skills are checked before fly is checked. This is normal.
2 - It can prog often if someone maximizes it, and that requires certain decisions that will leave them less ideal in other areas.
3 - Your aim/precise aim/opportunity strike *are* helping. His chances are just currently THAT good.

Additional comment - there are a number of things you can do to further reduce his chances, and even completely eliminate them.