First up I've added some watchers to get this a some immediate exposure
The actual issue of un-deletable blocks was raised several months ago shortly after the navigation blocks were first commit in fact. The idea of using a CFG variable was chosen because it was thought unlikely that people would want to start manipulating the blocks once they came to understand how important they are to Moodles navigation now and it was the most sure fire way to ensure that people were 100% aware of what they were doing, having to manually set a config var ensures that admins who are new or unfamiliar with Moodle don't just rampage off and delete all their navigation.
That being said managing it by capabilities may be a good idea, allowing admins to delete the block or assign the capability out as they desire.
Personally if we were going to do something about I would myself lean towards adding a userid field to the block instances table to record who added it and then add a capability to the allow deleting blocks you've added.
Undeletable blocks added by the system would still be undeletable however the admin could set them to just the site pages and then add or allow people to add the blocks to pages they desire. This would ensure that the admin could tinker to their hearts content, and we'd be safe in knowing that there was always an instance of the block even if it were just at the sit level....
Anyway just more ideas.
Watchers I'd be keen to hear your thoughts on this?