Expanding on this, one of the things ITA/QPX comes with is a dirty big availability cache that's constantly being primed (and paid for) by their customers (ie: Kayak, Orbitz, et al), who are now ironically not getting any traffic from Google :)
And they have this: http://itasoftware.com/pdf/BrochurePDF_DACS.pdf
One of the bits ITA/QPX got really right was smart availability caching (http://hasbrouck.org/blog/archives/001880.html) -
I would think they can do the fare search/assembly in realtime with their infrastructure, but they're relying on cached availability, hence the limit to "popular US cities" at the moment, to keep caches fresh enough within the practical throughput limits.