A group of friends were playing and really enjoying this game but suffered from these may problem. We all fired up Visual Studio and started debugging while playing and found the problems your discussing, but the problem doesn't have a simple "throw more threads at it" solution because of the deterministic nature of the game simulation relying on the path finding.
What we were able to do was put a hack into the path finding code that bailed on one of the loops after X amount of steps. It made complex paths less accurate (clicking units across the map to attack far away) but actually made the game playable. We could actually control our units whereas with the lag it's completely unplayable late game with 3 players and 3 AI.
Could you at least submit a diff of whatever you changed ? There are quite some changes planned for the Pathfinder see D13 on code.wildfiregames.com. But it might help any way :) Making a patch (diff file) shouldn't take you more than ten minutes :)
What we were able to do was put a hack into the path finding code that bailed on one of the loops after X amount of steps. It made complex paths less accurate (clicking units across the map to attack far away) but actually made the game playable. We could actually control our units whereas with the lag it's completely unplayable late game with 3 players and 3 AI.