I was going over my current missions and saw that the log still had the misssion open to build a winter shelter at one of my cities. I checked that city, and sure enough it already had a winter shelter built. I can no longer advance in the main quest now, in an otherwise very enjoyable session.

What happens if you tear it down and rebuild it?

Nothing, from what I read the issue seems to be that the mission city needs to be the first city it's built in or it doesn't complete, and in my case I also made a shelter in another city first.

Those threads were quite old, yet the bug persists, not impressive to have to throw away a game after 150 turns.

Does it always happen? I'm sure I've completed the Vaulters quest recently. Bugs that are intermittent are hard to track down.

I've only done it the once recently.