This is often impractical to the point of being impossible. Rather than doing this, perhaps designing a system where all PII is hashed through some sha method,

This is often impractical to the point of being impossible. Rather than doing this, perhaps designing a system where all PII is hashed through some sha method, and a a custom ID/salt for the user. If they ask you to delete you say sure, and remove that one relationship. This will screw up searching and indexing data though.