To give you a slightly better sense of the costs involved in an A* search and how they proliferate when spaces are open rather than confined, imagine that you are trying to reach a rock 10 spaces north of your current position, but in three completely different spaces:
1) You are at the end of a 1-space wide, 10-long corridor. At the other end is the item you want. In this case A* will find the object in exactly 10 steps, which is as good as it is ever going to get.
2) You are at a 4-way intersection with the corridors going off 20 spaces in all directions. The item is 10-spaces north. In this case you are going to find the object in about ~40 steps (A* has to search down all 4 corridors at once - it usually doesn't make any assumptions about what direction the object is in!)
3) You are standing on the surface, with nice green grass in all directions. The item is 10 spaces to the north. In this case basic A* is going to find the object in approximately ~400 steps - it has to search the entire square volume around you in concentric fashion before it finds the object! This is why a large starting embark area can have such dire consequences for pathing. Srlsy. 0_o;
Now, there
are A* optimizations that can allow for much faster searches in some conditions like the open field, such as favoring steps that move towards the object, and making ones that move away from it more expensive, for example - but those search optimizations are making assumptions that might make other searches much MORE expensive, so there are usually trade-offs for this kind of thing.
There are also multi-layer A* concepts where the entire search space is broken up into large sections of 'geometry' that can be stepped through extremely quickly to get close to where the target is, but these implementations are quite complex and can take up a fair amount of memory to boot, so I have no idea if they are used in DF.
In a game like DF where the paths are frequently convoluted, I suspect that A* makes relatively few assumptions - but you'd have to ask Toady about the details.