One runs out of spectrum the way you run out of patience. While there is a supply of it, metaphorically speaking, in practice it’s a matter of the behavior of agents (radios) in a given context – just as patience is a matter of how one person, with certain proclivities, reacts to the actions of another. The outcome depends as much on the attributes of the agents as the details of the context, and both are constantly changing.
“Spectrum” is a useful fiction that is used to talk about the management of radio operation. As I argued in De-situating Spectrum: Non-spatial metaphors for wireless communication, this usage is grounded in the spectrum-as-space metaphor, and in particular the spectrum-as-land variant. However, there are other viable metaphors for radio operation, such as thinking about coordinating radio regulation as similar to trademark: an infringing trademark that confuses a customer is like one radio that causes interference in another. A radio license is like a trademark; it enables one to prevent harmful interference by others.
However, the spectrum-as-land metaphor is pervasive. It appears in debates about how best to “manage spectrum”. Opponents of unlicensed , for example, claim that it leads to a tragedy of the commons. However, there is no tragedy of the commons with Wi-Fi, because there is no commons; that is, there is no underlying, essential resource that bears any resemblance to land in Hardin’s classic analysis, or as far as I can see, to what either lawyers or economist mean by “a resource” (assuming you can pin them down long enough to extract a definition). One can measure land in acres, and sheep in heads. A moment’s thought will confirm that there is no agreed way to measure “spectrum”: it’s not MHz, not MHz/m^2, not MHz.m^2, not watt/MHz or watt.MHz or watt.MHz/m^2 or watt.MHz/bps.m^2 or … And this doesn’t even begin to address the role of receivers.
I suspect that the rise of the spectrum metaphor is related the entry of economics into radio regulation. In order for (neoclassical) economics to get purchase on a topic, it must have (or create) a thing to be traded; and since economics is the allocation of resources under scarcity, this thing must be a scarce resource. Just introducing radio licenses don’t seem to have been sufficient to operationalize radio operation in economic terms; there need to be something which is licensed, or to which access is licensed. “Spectrum” fits the bill; it’s reasonably stable, and given the spectrum-as-land metaphor, sufficiently thinglike.
An interesting analogy is the creation of individual transferable quotas (ITQs) detailed in Petter Holm’s “Which Way is Up on Callon?” in Do Economists Make Markets (2007), edited by Donald MacKenzie, Fabian Muniesa, and Lucia Su. According to Holm, the ITQ model is an invention of neoclassical economics whose adoption was facilitated by the rise of fisheries resource management. As he tells it, it’s a complicated story “about the construction and stabilization of a heterogeneous network, tying the fish in with fishermen, echo integrators, log books, legislation, computers, bureaucracies, mathematical formulas, and surveillance procedures. It is within such a network that that the fish-as-fit-for-management springs to life, as a true cyborg: part nature, part text, part computer, part symbol, part human, part political machine.”  
The analogy to “spectrum” is pretty clear – the development of spectrum analyzers, the measurement program exemplified by the “spectrum occupancy maps” produced by SSC, NAF and others, and the stock analyst’s $/MHz.POP metric for analyzing auction results serve to construct “spectrum” as a manageable object of governance. 
I haven’t nailed down when spectrum entered the regulatory lexicon. It’s not used at all in the 1912 Radio Act, which mentions only “wave lengths”. The 1934 Act only refers to frequencies. However, Coase’s “Federal Communications Commission” paper (1959) cites Mr. Justice Frankfurter’s 1934 opinion in National Broadcasting Co. v. United States (319 U.S. 190, cited in Coase 1959), where the spectrum-as-space seems well established: “the radio spectrum simply is not large enough to accommodate everybody.” Frankfurter also articulates the resource notion underpinning subsequent development of the spectrum concept: “The facilities of radio are limited and therefore precious; they cannot be left to wasteful use without detriment to the public interest.” Spectrum-as-a-spatial-resource is therefore a pre-WW II concept; it evidently didn’t flow from the Coasian economization of radio, but I believe they reinforced each other. 
One can rightly ask why, given that the spectrum-as-land notion was well established in the Thirties, and Coase advanced the property rights case in 1960, it took another 30 years for the “propertization of spectrum” to be realized. I suspect that RF spectrum analyzers and broadband radio technology converged to bring about the “auction moment” in the 90s. It took time for both the analytical (game theory, law & economics) and engineering (real-time RF spectrum analyzers , commodity spread spectrum technologies) concepts to mature. They’re now well entrenched – and my quest to undermine the primacy of spectrum as an object of governance may be quixotic.
 Holm’s analysis is grounded in Callon and Latour’s Actor-Network Theory, which has been used to make the argument that economists “perform” the economy, that is, that economic models not only describe economic reality, but in part constitute it.
 Amusingly, it took a couple of trenchant critics of Callon to show how internecine politics in academic economics shaped the FCC’s spectrum auctions (Mirowski, P. and Nik-Kah, E. (2007) “Markets Made Flesh: Callon, Performativity, and a Crisis in Science Studies, Augmented with Consideration of the FCC Auctions,” in D. MacKenzie, F. Muniesa and L. Siu (eds.) Do Economists Make Markets? On the Performativity of Economics.)
 William Boyd introduced me to the notion of “objects of governance”.
 There seems to be tension in the law & economics community about this. Coase is a “property is a bundle of rights” man, which is decried in (2001) “What Happened to Property in Law and Economics?” (Thomas W Merrill and Henry E Smith, Yale Law Journal, 2001, Vol. 111, p. 357). Merrill & Smith advocate in rem rights that are referred back to things, as opposed to in personam rights that are arbitrary contractual arrangements. Thomas Hazlett has picked up on Merrill & Smith, and very much would like to treat spectrum as a thing which can be licensed unproblematically – but Coase got his rebuttal in at the start: “... what is being allocated by the Federal Communications Commission ... is the right to use a piece of equipment to transmit signals in a particular way. Once the question is looked at in this way, it is unnecessary to think in terms of ownership of frequencies or the ether.”
 Real-time spectrum analyzers for acoustic studies were available by 1957. Sri Welaratna’s "30 years of FFT Analyzers", in Sound and Vibration (January 1997, 30th anniversary issue) gives a historical review of hardware spectrum-analyzer devices; again, these are focused on vibration studies.