Well, the iTunes store came online in 2003. Not much of a stretch to foresee a marketplace for apps much like the marketplace for music. Whether it would be successful or not is another thing.
http://www.google.com/trends/explore#q=apps%2C%20mobile%20ap...