A number of ideas were suggested on the other thread about how we might go about solving this problem. In [3] Simon talked about perhaps enabling extra optimisations when the planner sees that the plan will cost more than some given threshold. That's perhaps an option, but may not work well for optimisations which must take place very early in planning, for example [4].
A small tweak on 3 to deal with 4. If the returned plan cost is quite high (say you estimate minutes+) you could just restart planning from scratch with all costly planning enabled, because even in the worst case (that is the additional options don't find a better plan), the total planning cost won't matter much in the grand scheme of things.
