It shouldn't be.
> that basically barely knew what info they stored about anyone
Aha, might have been the core problem, wouldn't it?
> It was virtually impossible to follow GDPR in that company
So, sounds like the regulation worked exactly like expected? If you're not following proper procedures for storing data, it should be hard to comply with a regulation that is trying to force you to have proper procedures for storing data.
A bit like complaining that fraud is hard because of those pesky police officers. Yes, this is the intention.
> The cookie-banner just seems like a very strange "security" measure
The whole cookie-banner thing is vastly misunderstood by companies, and at best just malicious compliance. Again, not the fault of the regulation but the companies who don't put users best interest first, but their own. Hard to blame them though, that's the purpose of their existence after all, most of the time.