It actually should be allowed. All that needs to happen is to add a generic user called deleted user or something and change all references to that user_id to the generic deleted user.
There has been a lot of aversion to this simple solution but you are correct that if a user doesn't want to be involved they should be able to be expunged. It will probably take some core hacking to get it to work perfectly though.