It would work with legislation if the loss of personal data of third parties induces extremely high fines that it simply isn't worth it anymore. Fines that could almost ruin even large players. Exception has to be business data since there is simply no alternative but the distinction isn't as trivial as it seems at first.

Since many would not be able to store user information they are reliant on people hosting themselves or at a service. I know it is difficult to explain that having control about your data is important and probably the most significant barrier. There are non-technical people that value privacy and data protection but most of them are highly educated.