"This kind of efficiency problem is something that looks ripe for multi-threading, but the main problem I had here is that all the world state of the game is held on the main thread and in complicated structures"
Crazy idea but I wonder if it would be worth it to have the pathfinding thread simply have its entire own copy of the mutable world state. Then when anything changes the world, both copies are updated roughly in parallel.
It would be a ton of duplicate work, but if you're on a machine with cores sitting there doing nothing... why not?
Thought here: If I'm reading this right the cache remains valid unless something is done to the world state. Thus how about dumping the cache when the world is altered, the separate thread simply sits there rebuilding the cache. If an object should move one unit but the cache isn't there simply note the movement but don't update it. Next time around when you find the entry in the cache you move it two units. Given the stated calculation times I would think the user would not see this.
Pathfinding in general doesn't allow a lot of multi-threading. You can do bi-directional search, but it doesn't always work as good as it seems on a 2D maze[0], and adding workers beyond the 2nd requires being really good at guessing mid-points, but it's doable in domains with sub-goals.
[^0]: Not the case here, but some domains branch too much when going backwards and can easily explore states unreachable from the start.
Yes, threading within your pathfinding code is hard. But in this case I'm suggesting running all of pathfinding on one thread separate from the main game thread.