There are simpler ways to do it than checking everything, but they trade tons of memory for their performance, just like your proposed solution in your original topic post would. If you store partial solutions, you do so with the use of some sort of table, and you trade the memory for storing that table to save the time it would take to generate the solution at run-time. If you find there are certain nodes that you always take for a given solution, then some sort of table might help. If you can't really tell up-front whether or not an edge will be part of a solution, then you're pretty much stuck because the table size grows exponentially.
Whether or not taking shortcuts will be useful depends an awful lot on your graphs topology & your edge weights.
For example, if air transit costs 1/100000th per mile as boat transit, and boat transit costs 1/100000th per mile as truck transit, then you can simplify your search a whole lot. You can do this because you already pretty much know that you take trucks to either airports or seaports, and only chose a seaport if there isn't a reachable airport. Your graph becomes mostly hierarchical at that point. Your 'simplification' could then pretty much keep a table of place pairs, A and B, describing that place A and B are nearer to each other than the sum of the distance between A and an airport and B and an airport. Since you know, because of the massive cost bias mentioned earlier, that this is the only situation in which you wouldn't use an airport, you can use your table to rule stuff out quickly. You'd further use the knowledge that there are more airports than non-airports, and thus a table like this is actually cost-saving. Your table also wouldn't blow up because you'll have a roughly constant number of places nearer to any given location than the nearest airport.
Check the table, if you find an entry then you run A* on truck roads, otherwise you run for A to it's nearest airport, then the airport search to get to B's nearest airport.
This is of course an unfair simplification, but you get the idea. If you have domain knowledge, you can simplify stuff substantially. This simplification comes not necessarily at making the problem easier, but leveraging domain knowledge to develop better A* heuristics and to adjust the graph topology from a naive solution. If you don't have domain knowledge, then you either write your program to discover knowledge, or you go with a general solution that doesn't require knowledge. Either way though, this is a wholly traditional search problem, and we're only talking the degree of knowledge you have regarding the topology of the graph.
Should be noted that A* pretty much requires some degree of domain knowledge for heuristic authorship, otherwise it just degrades into BFS which is absurdly ineffective on large graphs.
