This is exactly what happened with the AshleyMadison hack. In fact, users explicitly paid for a "delete my account permanently" action.. yet it was just that, a "deleted" flag added to the DB which eventually got leaked.