Very interesting thread, you made some fine observations that'll surely help us make the AI at least do a bit better ;)
I thought a bit about some of the things you mention about stalling and I have a theory that the AI decides to issue movement orders on a stack-per-stack tile-per-tile method which means it seeks a target for a stack and then only moves the stack to a tile if this tile decreases the (euclidian) distance to the target to the next integer (rounded).
This would explain your example where the stacks got stalled after an unsuccessful siege south of the forest (distance would be 7, if the stack moved right, still 7)
It would also explain the problem with 90 degree bends in roads that lead in a straight line to the target after the bend because the distance (in integers) wouldn't become smaller and they can't move diagonally because it'd take more movement points thus increasing the distance again.