I don't think most of the examples above fit into Eric Ries' definition of MVP:
"the minimum viable product is that version of a new product which allows a team to collect the maximum amount of validated learning about customers with the least effort."
The confusion arises because the examples given demonstrate some aspects of the LeanStartup methodology, but that doesn't make them examples of MVPs.
Sure, Yahoo was a manually created directory, but that wasn't because Jerry Yang wanted to create a "concierge MVP" to test demand. It was done manually because there was no other way to do it at the time.
Likewise Google when it started - it was minimal, sure, but it wasn't created to test the hypothesis "do people want a better search engine" - it was created as part of Larry & Sergey's PhD research thesis.
So, an MVP isn't just a "basic" version of a product that later becomes more complex. It's not something designed to test technical feasibility, it's not designed to see if the team can create a solution. It's a product that
only exists in order to help the team learn something about customers and their behaviour. Valuable things you can learn from an MVP include: is there any demand for this product?, what price should we charge? will customers find our product? does this ad copy work? etc.
From this list, probably the most useful question that an MVP can answer is "Before I invest tons of money in developing this product, how can I test if there is enough demand to make the investment worthwhile?"
A well designed MVP will do just this - it will focus on presenting customers with a solution to the pain that you have identified in your Customer Development interviews and seeing if they act in a way that shows intent to buy.
Think about Kickstarter - it's practically as a warehouse full of MVPs. People put up their ideas for interesting products, before they build them, and other people demonstrate their desire by supporting them.
It's important therefore to remember is that an MVP can be really, really "minimal". In fact it doesn't actually have to be a "product" at all. Many of the best examples aren't. Check out Dropbox's MVP story for a great example:
http://techcrunch.com/2011/10/19...)
By contrast, most of the examples given above are far from MVP. I very much doubt that the only way that Virgin Airlines could test demand for a new transatlantic service was to actually buy a plane and go through all the regulatory procedures required to start an airline.
Likewise craiglist. The fact that it has minimal features and styling doesn't make it an MVP. The goal of it was to provide "an email distribution list of friends, featuring local events in the San Francisco area", not to help Craig learn about whether people wanted a listings site. It's true that he learned just such a thing - but that was a byproduct, not the purpose.