The problem isn't to delete 1 piece of data 1 time. The problem is different people demanding thousand+ rows randomly spread out in your database deleted every day that is the problem.
Maybe a percentage will be better educated, and actually request data deletion here and there, sometimes but I don't thing anything is going to massively change in general customer behavior. The GDPR just gives the means to those who really want to control their data (which were there before, by the way, just not really enforced. Now that there's a number figure to the possible fine, now is everyone paying attention.)
The pessimistic case sounds like trying to remove things within hours.
It isn't an impossible problem to solve, but the GDPR is a significant time and a money burden that will especially be an issue for small startups that don't have millions in venture funding to spend on this.