The approach implemented for one PPM Client:
Create an custom attribute Parent Project
Have Auditing turned on the custom attribute Parent Project
Have a custom Process that is regularly run that updates (when required) the custom attribute Parent Project.
Though you won't have the full history of who removed the parent relationship from the Hierarchy, at least you will have the history of what it originally was.
Also review if you need the 'Hierarchy Tab' enabled on your Project Layout. If not, disable it, as this will be one less place the user can remove the Parent (though note, it can still be modified on Sub-Projects page). For the above PPM client, we have a Project Admin Layout which has 'hierarchy' enabled, so that they quickly modify required project to enable the hierarchy tab, modify the hierarchy for that project, and then set it back to Project Default Layout where the 'Hierarchy Tab' is disabled.