Earlier quoted context omitted.
I've been thinking about this a lot. But the problem is that such a service would have to violate EULAs of many popular services like facebook and twitter.
EULAs are never legally binding, and especially not for someone who is 1) not currently a consenting user, and 2) invoking a right. So in the EU, if current legislation projects bear fruit, a case could probably be made for implementing this under the protection of the right to be forgotten, and there would be very little those services could do to prevent it.
Violation will certainly give the social media cite grounds and desire to delete the false profiles though.