Glad you're feeling less confused. I should point out that I don't work in legal, and these regulations are very much open to interpretation even by those who do, so my understanding is exactly that - my own interpretation.
That said, we have some very large clients who GDPR compliance is important to, and as well as development services we offer hosting and server management services for these clients so as you can imagine, I've spent a considerable amount of time on the run-up to GDPR trying to get my head around everything. While I can't make any legal gauarantees that there are no flaws in my advice, it should be pretty accurate.
@XeduR, I'm going off topic now but ref your timestamp based approach to ID generation - I learned the hard way last week that as miniscule as a possibility seems, you should still expect it. One of our client stores generates an incremental order number during checkout, by basically looking up the last generated number, incrementing it, and performing another lookup to make sure it definitely isn't yet used (autoinc fields aren't an option on this occasion). This runs in a loop until a unique ID is generated, and then a new database record is created for the order, using that ID. The whole thing happens in nanoseconds, and you'd expect it to be pretty bulletproof, huh? Nope. 51,000 orders later, we found that 56 order numbers has been used twice! This is a store that receives approximately one order every 3 seconds during peak time (the run up to Christmas), so two people hitting the checkout button at precisely the same time is actually a common occurrence. Combine that with a web server that runs multiple simultaneous PHP threads and suddenly it's very possible for two threads to determine the same order number is available at precisely the same moment in time. Not good!
Our fix was to generate a second random 2-letter code when the user first lands on the website, so that when that user hits the checkout and the above system kicks in, the 2 letters that were already assigned to that user when they landed on the site can be appended to the resulting ID. Now when two users invoke checkout at exactly the same time, this can only result in the same order number generating for both customers if they also happen to have been generated the same 2 letter code when they both landed on the site, which reduces the likelihood considerably.
So learn from our mistake and always add something random into any algorithm that would otherwise produce the same result of executed twice at exactly the same time. As unlikely as the scenario sounds, with enough active users that chance is just too great.