David Finch's solution:

First, for each target, it creates a rough cost map at the original text resolution (173x173) from each block to the target block. Some special rules are included for handling certain types of narrow obstacles.
Next, it estimates the best order to visit the targets. It seems to give pretty good answers in a short amount of time.
Finally, it traces the path. It sort of feels its way around rather than doing a full search. I messed around with combinations of the two and decided that a 100% feeling around strategy gave the best results for the time taken. It's very fast, and feels about 10 moves ahead, but does poorly on the random map where precise, rapid direction changes are needed.

It should be able to handle larger maps, with more targets, but I'm not sure just how much larger. At some point, integers will overflow and such.

Source code:
http://mytsoftware.com/misc/mars.c