[mic47]

> In order to "delete" my phone-shadow-profile, facebook needs to remove my phone number from their internal copies of my friend's contact lists.

This is (potentially) not viable. Your friend's contact list is not your data, it's their data (about you) and they store it on FB servers. Right now it's probably used only for ranking and friend suggestion, so what you suggest would work. But if FB would decide that say messenger should work also as contact sync app (it already allows you to send SMS to people in your contact list), this would cause that your contact could not be synced, and really break user experience, as you would be able to delete your phone number from your friend's phone books.

More philosophical question: if you should be able to do that [delete your phone number from your friend's phone book on FB], should you be able to do that also from google contact sync server? From gmail? From your friends phone? Or from your friends physical (manually written) phone book? Where to draw a line, or how to approach this?