Maybe workshops could have multiple behaviors? Suppose at every season-change or once a "day" or whenever would be appropriate, each workshop does the elaborate pathfinding check to every individual stockpile set to use workshop-appropriate materials, and records the stockpiles in order of preference.
Then, when a job requires a material, the workshop checks each stockpile in order of proper distance for the material it needs without calculating any paths or running any algorithms beyond "what's the first suitable material in this stockpile?". If there's nothing in the stockpiles, then it goes hunting the map using a more intensive method.
/not a computer scientist
...actually, not a bad idea. When a dwarf does a job, and it is to a stockpile not already accessed by that workshop, the workshop stores a pointer to the pathing object. Then subsequent dwarves can access the path to the stockpile they want from the workshop that they are doing the job for. You can then make an optimized algorithm for searching stockpiles, since there are some general assumptions you can make about them (usually comparatively large and obstruction free).
If the list of stockpiles is stored in a binary tree, you can find out if the stockpile has been accessed in O(log(n)) time, and if it has, the pathing step takes O(1). Say that the rate of new path calculations follows an exponential decay with the age of your fortress,
and over time the pathing time becomes more or less constant. Huh.
And back to the game. Yeah! SO CLOSE!
Edit: Oops, I did my math a little wrong; over time pathing would approach O(log(n)), not a constant since you still must look up stored paths in the workshop.