You can do a MVP to validate pretty much any hypothesis that is key to the success of your startup. Strictly speaking an MVP doesn't have to be a product, just some aspect of your business that you are uncertain about.
Let's say that one of your hypotheses is, "What kind of demand is there for our service?" There are many way to set up an experiment to test this out, but you need a very fast and cheap way of doing this with the minimum of resources.
One approach would be to create a very simple one-page site describing the service. And by simple I mean something something fast and dirty that takes hours to finish and not days. Obviously, the product that you're showcasing doesn't exist at all, you just have some copy, screen shots and a mailing list sign-up form where people can get notified about updates. To market the site, you could use popular approaches such as Google Adwords or just start bloging/tweeting about it.
Based on the data you gather - web statistics, mailing list sign-ups, emails, tweets, blog comments, etc - you should be able to answer the hypothesis with confidence.
So where is the MVP in all of this? Well, it would be everything required to answer the hypothesis, which in this case means setting up the site, mailing list, marketing, gathering data, etc. Once you can answer your hypothesis, the MVP is over and you can start working on a new hypothesis and MVP cycle.
Virtually any question you have can be solved this way. In fact, some people would insist that all fundamental business assumptions must be managed like this because this approach gives you the hard data you need to shape the future of your startup.
Although I have my doubts about the validity of The Lean Startup methodology, I think MVP as a concept is very potent. You should read Eric Reis book if you want to gain a better understanding of the methodology. For a much more practical approach, I recommend The Four Steps to the Epiphany by Steve Blank [ http://steveblank.com/ ]