Things like the utility homosexuals get from freely expressing themselves, and the various Public Choice problems with implementing the system. But I also think the first premise is false, and third is at least a simplification.

Yes, but that doesn’t mean we couldn’t adopt the nearest stable system, which could be Libertarianism without sexual freedom.

I would bite the HHH bullet and say that we'd have to do something about it. Things like SeaSteading provide non-coercive alternatives, in basically the same way that making property rights totally secure would prevent being outnumbered being a problem.

However, Minarchists are quite happy to accept taxes to defend liberty, and I know the President of the Oxford Libertarians would accept conscription, and I don't think there's that much difference. It may well be that we should adopt a consequentialist deontology: we act in such a way as to maximise rule-following. The danger here is that in breaking rules to try to enforce them, we might undermine them further.

In general, I don't think Libertarianism has much chance without a culture of individual responsibility, quite possibly family-based.