Why do people expect data about themselves to magically disappear from the Internet? One should always assume that everything you communicate online (explicitly or not) has the potential to exist forever.
Because we are talking about proper legal entities here. If I want my data deleted, they should have the means an the will to do so. Nothing "magical" at all.
It is not as if I am asking "the internet" to delete my stuff, but "facebook", "google" or "okcupid".
If they agreed that they would delete everything they know about you at your request, sure. But most of them don't, which means you can't do anything.
Companies should not be forced to implement ways to delete data about users. That's just silly.
Why do you want them to delete the data anyway? To me, it sounds silly and looks like some kind of censorship. Embrace transparency and live with the fact that what is public remains public.
It is not as if I am asking "the internet" to delete my stuff, but "facebook", "google" or "okcupid".