and in most modern societies the state's entangled enough with the institution of marriage that I'd expect a purely private claim to marriage status to feel like a cheat to many people.

Why is this? In Slovenia I see non-government institutions doing such marriages all the time and being taken seriously by others. The institutions in question being Churches, since religious marriages are not legally recognized here. Some people only do the "Church wedding", most also do the "State wedding".

I don't see a strong reason why other non-government institutions couldn't carry the same kind of social legitimacy.