What’s actually happening when permalinks for custom post types suddenly stop working

The answer is as simple as not helpful. You have plugins which have bad code, and in any complex system with many parts not controlled (at least not the code) by you, it will be very hard to debug how a global resource get corrupted.

The way to avoid it is to stop auto updating things, and properly test every update on a staging enviroment, so if something goes wrong and you might need to update the permalinks you will at least know that in advance.