limberg
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.