Right then. So I spent a few hours running different game setups and timing how long it takes to AI to move between turns. At times it went all the way into the 90 second range. That actually happened with normal resources instead of dense, so there goes that theory. I did manage to get it stuck again 28 turns in on a tiny map, with few monsters and one opponent. I'm sure it was stuck, and not just taking a long time... unless it took more than 2 and a half minutes to think about doing things. I cheated and looked at what the AI was doing, he was just standing there, full moves unused. Maybe it's worth noting the AI was on an easier setting, which I think it was in a few other cases where it got stuck.
So, in other words, I found bupkis. Not even the turn times are consistent, there was 55-8-37s at one time. I thought maybe starting the game fresh would decrease the times(exiting before staring new), and it did, on turn 1, but from turn 2 on, times were higher than from game started with CTRL N.
In hindsight, I should have used predefined maps instead of random ones. I stink at bugtracking.