I would think the limiting factor is availability. You can pre-compute valid fares between cities super-fast with sufficient computing power, but you're still (somewhat) limited by the rate at which you can update availability, which _still_ has to be polled from airline systems (to some degree) and can't give you answers in <400ms :)

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.