Wow...I'm still quite surprised that a department would pass on a promising scholar in favor of a less-stellar candidate simply because of the cost of a plane ticket. Publication records DO have an effect on a department's standing as a research institution, don't they? Wouldn't most departments be interested in landing the best people available, even if it means spending a few hundred more dollars during the search?
Colleges often do amazingly stupid things over trivial amounts of money.
That said, I think it also depends on whether a search can generate a sufficient pool of qualified candidates without having to fly people in from foreign countries -- and perhaps more importantly -- without worrying about H1B visas. (Remember that H1B visas are really supposed to be for cases where a qualified US citizen/permanent resident cannot be found.)