I had a hunch and tried to find my way through the AI-clients code and I was unable to find a line that clears the list of orders at the beginning of a turn.
The orders set is cleared immediately after they are sent:
(StartTurn is called client-side to end the client's turn, which "starts" the turn on the server).
On the server, all sets of orders are deleted after being executed:
// loop and free all orders
for (std::map<int, OrderSet*>::iterator it = m_turn_sequence.begin(); it != m_turn_sequence.end(); ++it)
it->second = NULL;
And no orders are sent back with a standard turn update mesasge, so the AI client has no built-in memory of previous turns' sent orders.
Could it be that the AI sends not only the new orders but all old orders as well, which we just don't notice most of the time, because the older move orders are overridden by the new ones all the time?
I don't see how this is possible, though I could have missed something and didn't write most of the relevant code once inside the Python-exposing parts.