First off, the GDPR just harmonizes existing data protection laws, and increases the associated penalties to give those laws teeth. If you need to do something fundamentally new today, you probably broke these laws yesterday already. Stop whining because you feel forced to comply now, just due to the fines having been increased. That's a basic risk of entrepeneurship.

Next, something like the deletion right has to submit to other laws that mandate data retention, like having to keep sales and bookings records for 10 years due to tax laws. If you do a cascading deletion in your data set, you're probably breaking these, so flagging records as deleted, or moving them to an archive to comply with these other laws still is perfectly find.

So this is just another regulation a startup has to think about. It's way easier than, i.e., tax laws, so please. Just stop panicking -.-