ladypine: Neither of the examples you cite show a failure of pareto efficiency, in fact quite the opposite. I'll explain.
In the case of an auction, any price below the second price wouldn't be pareto efficient, because the seller could sell the item to someone else at a higher price and both the seller and the new buyer would be happier. Pareto efficiency isn't unique in this case, because the high bidder purchasing with any price between the first and second bids is pareto efficient.
(Yes it's possible to make more money selling on ebay by setting your minimum bid increment to a humongous value. At some point I'll get around to writing about ebay at length.)
The reason to go with the second price instead of some amount more (which is how ebay does things, irritatingly enough) is to make it less gameable, however some gameability remains. Specifically, the seller could inflate the minimum price to anywhere between the first and second price and be better off. This is impractical under many circumenstances, but is very important with only two (or one!) bidder. Note that gameability is only a problem in the situations in selecting between different pareto efficient solutions, so there's no weakness to it as a technique here.
In the case of stable marriage, there is a straightforward algorithm for finding all stable solutions based on pareto efficiency. For each person A, if A's first place choice is B, then for every C which appears below A on B's list of preferences, scratch B off C's list and C off B's list (this is justified because if B were paired with C then we could change the pairings to have B paired with A, and both A and B would be happier). Repeat until you can't simplify any more. At this point, participants will be in cycles, in which B is first on A's list, C is first on B's list, D is first on C's list, etc, until we get to A being first no somebody's list. Because of the gender difference, these cycles will always be of even length, so for each cycle we have to decide whether the males get their first choice or the females get their first choice. Note that this is a choice between different pareto efficient configurations, the appropriateness of pareto efficiency as a criterion is uncontroversial.
In practice, even on random data, this technique does such a good job of pairing up people that there's hardly any arbitrariness in final pairings. In the medical example a study was done and found that only a miniscule number of students would be assigned elsewhere in students's choice, so the algorithm was switched to that for good PR.
A bit off-topic, I'd like to point out that It's utterly stupid that 'the match' was so controversial for so long. I at one point solved stable marriage on my own because it's an interesting problem, coming up with the above algorithm, and after a little bit of testing realized how little difference male versus female choice makes. That was only a few days's worth of work. Let this be a lesson to everyone that if there's a big controversy which a simple study can shed a lot of light on, do the damn study.
The stable roommates problem doesn't always have a pareto efficient solution, for example there might be a loser who's put last on everyone else's list of priorities, but the above technique can be used to make an algorithm which works very well. Note that stable marriage is just a special case of stable roommates where all the males rank all females above all males and all females rank all males above all females.
