If you think of obtaining prices as being akin to 'indexing', then what metasearch engines are doing is building up a search index for flights. And not all price sources necessarily charge for data (do Google pay to index Hacker News?)
Flight prices become stale as do indexed web pages - and as long as the user doesn't pay a transaction price for any search activity, then you can re-check pages based on user activity - in the case of travel, re-check the price once the user nears the booking phase of the funnel.
As noted though, sparseness of travel queries is certainly tricky! The 80/20 rule applies to some extent, and popular routes will be the ones which have the best price cache.
Another disclosure: I work for Skyscanner (our core is a flexible travel search engine)
Therefore, rather than only considering the single lowest-cost edge on the graph (that is, an A-to-B flight to an interesting place), you could consider lowest-cost paths, using a pathfinding algorithm (secondarily weighted by the popularity of intermediate cities/vertices as temporary destinations.) Thus, instead of going to city X, it would recommend going to Y, staying a month and taking in the local culture, and then finishing the trip to X with a short, local flight in the off-season (or any other method of travel—it could integrate with Google Maps to see if it would be cheaper to drive between each pair of intermediate nodes than fly.)
I went back and forth with Bill O (at Kayak) while leveraging their API, and know the cost/query was fairly high a few years ago. I suspect it has decreased, but probably not to the point where the processing power needed for massive permutations and cost/query makes this any more feasible.
I set up a proof of concept in 2006/2007 that still works (most of the time). I ended up using Flash/Flex front-end to overcome the number of browser HTTP connections (and keep some of the processing on the client). I'm not sure this actually helped the server or not b/c I never did any testing. I also limited to "where can you go" (multiple city pairs) and "when should I go" (single city pair with multiple dates), but not a combination of both.
Feel free to take a look. It will shut down after the max number of queries/day is reached.
Availability of data APIs turned out to be a big hurdle for a bootstrapped startup. The market is still up for grabs. Here is another attempt by an Indian startup:
Needless to say, the number of combinations of these variables precludes doing any kind of exhaustive search (especially since you're being charged per query). And availability is constantly changing, so your results are potentially out-of-date the instant you receive them.
Given these restrictions, the only way to support such broad-ranging queries as "where can I go for less than $1000?" is to cache results from previous searches and attempt to guess at the answer. Which is why, when you start narrowing down date ranges and choosing more obscure airports, the results quickly become so sparse as to be useless.