If they are not doing their job, (and you are not content with their reply), you then appeal to the Data Protection Authority (DPA, Privacy Regulator in the country). The DPA has full powers of subpoena (and a whole lot more), and are not to be trifled with.
So how to get my PII deleted from FB's servers, for example? FB mines other people's phones for this data continuously, so will they setup a blacklist, so that my phone number will not get mined ever again from other people's phones? Blacklist will have to contain my phone number in order to work. Somewhat self-defeating. Hashing will not do much, because the search space is so small.
Also, they may have my phone, and some guess at my identity. Providing a much stronger link between my identity and my various other identifying information (phone no, emails, ...) to random shady companies and hoping they'll use it to delete data they may have on me... uh. It does not add up to something sensible.