In his EconTalk podcast, Hal Varian, Chief Economist with Google speaks about Search amongst other things.
..search is about two things. Precision and Recall. He then defines precision as “off the number of documents retrieved by a search result, how many are relevant” and recall as “off all the relevant results, how many were retrieved”.
This in my opinion is very important aspect. Before we take on a problem to solve, we need to have the exact definitions in place.
He also spoke about co-evolution of technology and users. He said that any technology and its adopters evolve rapidly with time. He took examples of cars and extended it to search engines.
..users are getting more skilled at entering search queries. This helps both user and the search engine in delivering results that are high on precision and recall. And thus making the experience better for the user.
This probably explains why most of the user-dependent (user generated, network effect etc) businesses remain in beta stages for long times (gmail is still in beta). Till the time both (business and users) evolve and are mature enough to help each other, system has to remain in beta.
Lessons? Help your users evolve. Give them tools of the trade. They would need some hand-holding to learn initially. And then they would need the freedom and independence to play around with the system before they start making effective use of the system. And same goes for the system as well.
Please note that the definitions might not be exact (since I took notes while listening to the podcast), but the essence has been preserved.