KPN does al government telco stuff because it used to be semi-public. As such, they have a lot of institutional knowledge behind this kind of thing.

I would not trust any other telco to do this better. It seems to me the issue is the commercialization/privatization of KPN. Instead, we should go back to a more semi-public KPN that is assigned to cover this form of critical infrastructure.

Or alternatively, we should not have any telco be a single point of failure.

This might be your first instinct, but a new contractor would have to gain the knowledge KPN did on preventing these outages, there is no guarantee any other company would have better uptime.

Reminds me of the quote or story that someone rather hired an ops engineer that accidentally dropped a database than someone who didn't. As the first one would go at more length preventing to do it again.

Wouldn't it make sense to use several phone companies so you can easily switch to another as backup in case of problems?