I think the "vehicle protection system" entails more than just a steering lock.Good to see your problems finally solved but it leaves me a bit confused as to why I was seeing the same message under different conditions. I never had a problem starting and only saw the message along with the hill holder/vdc once the car had been run for 10 minutes or so, and then, only if I accelerated a bit rapidly. I knew the brake pedal switch was on its way out, but this message would appear reliably without touching the brakes. Once the switch was replaced, the message never appeared again so there must be some convoluted logic somewhere in the engine management.
I believe it also includes the immobilizer, alarm module, if present, and it is linked to the ECU and body computer. I can image any random (combination) of faults can trigger the error message.
i.e. if there is an issue with the starter system (pedal sensors disappearing after power-on) the immobilizer might be disabled for safety issues. This would in turn trigger a fault with the "vehicle protection system".
Similar to the steering lock sensors issue. If the steering lock sensor/body computer cannot 100% be sure the steering lock is disengaged, the car will not start.
Starting issues because the steering lock "disengaged" sensor is fubar? yeah that would be a long, very long search without reading the error codes first.
Most important thing here is to read codes before starting replacing or working on things. In all the issue's I've had it was clearly stated by the different computers what component or system was triggering the issue. Most EOBD computers will allow you to actuate certain actuators or live monitor sensors. That would help you pinpoint what components are faulty without ever touching a toolbox (apart from the Philips head screwdriver you would need to open the fuse-box).
The €40 + €15 I spend on AlfaODB and a chinese bluetooth ELM OBD reader has been well worth it in time saved alone. Not to mention proxy alignment costs saved in dealer fees or resetting the computer after maintenance I've done myself.