As the comments above suggest this is not a straightforward question to answer. However just a quick two cents to add to this, chasing the perfect may not be the correct solution either. For some folks a 80% solution may be good enough.
Not to start a holy war, GSAK has a CacheRoute3 macro that uses google maps as a backend for computing distance. This has been very useful to me in computing routes to complete Delorme challenges and other similar challenges in the states. It is not without drawbacks but is still very helpful.
Drawbacks include the list above. As the traveling salesman is NP hard, somewhere around 100 caches, the performance becomes very slow. Optimal is not required but something close to it would be nice. Also the use of parking coordinates (or multiple parking coordinates) are not considered.
Beyond that, there have been complaints when I use it in a group that it does not consider the side of the street.
That said, with all the faults and shortcomings, it is a useful tool. But as said above, is it better to scratch everyone's itch or only some folks itch from a support point of view?