Well now that you've seen them I can talk about it more.
The problem isn't the order the the AI is performing the orders in. The problem is the turn move replay. The ships are cloaked at the begining of the turn, it's just the turn move is a little funky and shows you their Last turn before they disappear. I believe if you happened to have a ship in the next sector over they would pass over them without initiating combat just as if they were fully cloaked. Although that needs tested to be sure. What I have tested is that what you saw is not dependant on the AI. If the player had been in control and cloaked the fleet and moved it you would have seen exactly the same thing. The ships would have moved and
then cloaked in the turn move log.
Geoschmo