The thing is...contact details aren't really private information, basically by definition.
The distinction is contact details privacy is based on the desire not be interrupted by people you didn't agree to be interrupted by - i.e. it's a spam problem - and realistically to solve this requires a total revamp of our communications systems (long overdue).
The basic level of this would be forcing businesses to positively identify themselves to contact people - i.e. we need TLS certificates on voice calls, tied to government issued business identifiers. That would have the highest immediate impact, because we could retrain people not to talk to anyone claiming to be a business if there phone doesn't show a certificate - we already teach this for email, so the skill is becoming more widespread.
A more advanced version of this might be to get rid of the notion of fixed phone numbers entirely: i.e. sharing contacts is now just a cryptographic key exchange where I sign their public certificate which the cellphone infrastructure validates to agree to route a call to my device from their device (with some provisioning for chain of trust so a corporate entity can sign legally recognized bodies, but not say, transfer details around).
This would solve a pile of problems, including just business decommissioning - i.e. once a company shuts down, even if you scraped their database you wouldn't be able to use any of the contact information unless you had the hardware call origination gear + the telecom company still recognized the key.
Add an escrow system on top of this so "phone numbers" can still work - i.e. you can get a random number to give to people that will do a "trust on first use" thing, or "trust till revoked" thing (i.e. no one needs to give a fake number anymore, convention would be they're all fake numbers, but blocking the number would also not actually block anyone you still want to talk to).
EDIT: I've sort of inverted the technical vs practical details here I realize - i.e. if I were implementing this, the public marketing campaign would be "you can have as many phone numbers as you want" but your friends don't have to update if you change it. The UI ideally would be "block this contact and revoke this number?" on a phone which would be nice and unambiguous - possibly with a "send a new number to your friends?" option (in fact this could be 150 new numbers, one per friend since under the hood it would all be public key cryptography). I think people would understand this.