I think it depends on your definition of "out nowhere". In most business circles Amazon is seen as a radical strategic innovation that obliterated the traditional book business (almost). But if you lump it in the same category as "selling things on the net", then it is pretty obvious.
No body saw Page rank's impact, but if you think it is obvious that reputation plays a part in relevance, then again page rank is just an obvious thing that built up over time.
The iPhone/Pod/Pad/XXX - if you say "simplicity" is the obvious killer in any product then they well it should have been obvious...
and the list goes on...
I think in hindsight a lot of what made the strategic innovations seem so obvious was well hindsight. It reminds me how MBAs are so great at explaining what has happened but are terrible at providing a plan with 0 uncertainty!