The origins of the phrase 'spontaneous order', and the origins of the idea   
as applied to human societies, do not have to be the same  
  
Some such idea (without the phrase) is surely present in Smith, but its   
origins could be traced back further. A simple example might be Hume's   
treatment of the balance of trade. Attempts by states to manipulate the   
balance of trade are likely to fail. Data is lacking, so that it is not   
even possible to determine what the balance of trade is. Nevertheless,   
monetary metals end up distributed between trading nations in proportion to   
levels of activity so as to keep price levels in line. Looks both   
spontaneous and orderly to me.  
  
In the 18th century (and earlier), the order of nature was often seen as   
the result of divine creation, so perhaps not wholly 'spontaneous'. Mill's   
use of the phrase is in this sort of context, but criticizing the idea that   
the spontaneous course of nature has some special status. See  
http://www.la.utexas.edu/research/poltheory/mill/three/nature.html  
and search for 'spontaneous order'. It doesn't have much to do with Hayek's   
idea, though the phrase might have struck him.  
  
If human action led to coherent (perhaps in some sense optimal) results   
this might be spontaneous in the sense that it is the result of   
decentralized human action without any centralized human coordinator, but   
it might also (in an 18th century view) be the intended result of design by   
the 'great architect of the universe', or whatever. Whether that counts as   
spontaneous, I wouldn't like to say. Smith (and others) may have thought   
this way.  
  
Tony Brewer