One cannot address the initial question without starting with an agreed definition of preposition.
A basic definition, which covers prototypical usage of members of the word class, and an accessible form of which is usually the first introduction to the subject given to children, is 'words used to show a spatial relationship between two referents' (eg The rabbit is in the box.).
This is rapidly seen to be an unworkably narrow definition; there is a broadening to the identification of the use of prepositions in analogous directional (rather than just locative) constructions (Peter put the rabbit into the box.) and temporal constructions (Peter left after the match.).
However, it has been found convenient to use analogous constructions in 'peripheral' cases - not involving space / time relations - and these can be considered to a lesser or greater degree metaphorical (with regard to the prototypical usages). The preposition now is defined from the perspective of grammatical function rather than from conceptual considerations, and this dual role causes confusion about the nature of the preposition.
'A preposition links nouns, pronouns and phrases to other words in a sentence' is the broader function-based definition / descriptor offered by by Heather MacFadyen - but this obviously isn't precise enough to exclude coordinators (eg and), complementisers (that), sentence connectors like additionally, and others. I prefer the requirement of 'within the same sentence', though - the claim for 'intransitive prepositions' (eg CGEL) is, I believe, ill-founded.(See http://stl.recherche.univ-lille3.fr/sitespersonnels/cappelle/Pdf%20versions%20of%20papers/The%20particularity%20of%20particles.pdf)
Prepositional phrases where the preposition involved seems 'arbitrary' are often, if not always, the result of changes over time in phraseology and/or what exactly was brought to mind when people first used the expressions compared with which, if any, picture is conjured nowadays. We are now left with (to us) unpredictable - idiosyncratic - set phrases. Idioms.
There is debate over the degree of 'decomposability' - how much value there is in analysing individual words - for various idioms. (See Fixed Expressions and Idioms in English: A Corpus-Based Approach by Rosamund Moon.)
There was a school of thought that perhaps over-emphasised the 'word-with-spaces' analysis (so ship of the desert = camel, each of which denotes a single referent described by a single lexeme, no matter whether this uses 1 word or 4). This approach has value (but does not give the complete picture). Using this model, as kiamlaluno suggests, on fire (= afire) would be treated as a single (two-word) lexeme corresponding to a (predicate-only) adjective. (Where collocation ends and compounding begins is a different matter!)
At http://grammar.ccc.commnet.edu/grammar/prepositions.htm is the statement 'Prepositions are sometimes so firmly wedded to other words that they have practically become one word.' Admittedly, the authors are there referring to many (noun etc + preposition) constructions, but the statement is equally true for some (preposition + noun etc) constructions, as here.