You must work with some pretty poorly organised companies. I work with a lot of French, Belgian and German companies and they pretty much all have proper procedures and tools for this.
In France in particular the right to access/change/delete any and all data a company has on you was there long before GDPR (by decades) so most serious company are well used and prepped for it.
They range from start-ups to national champions, but I won't disagree with you on the poor organization of most European companies point. Everyone one re-papered existing systems to some degree of compliance. Given nobody agrees on what full compliance is, they're all right in their own ways.
I wasn't making a point about European companies in general but about the ones You work with personally. Because they don't seem to be like the usual norm for European companies, that do have procedures and tools for this, unlike in your experience.
In France in particular the right to access/change/delete any and all data a company has on you was there long before GDPR (by decades) so most serious company are well used and prepped for it.