Not sure if that's of any comfort, but don't feel singled out: this naming issue happens _all the time_, in all countries, to everyone. I'm French, and had constant issues with naming and identification, whether I lived in western Europe, Eastern Europe, or Asia.
- I have acute (é) accents in my first and last name. This seems to create different problems for each system my name is interacting with. Sometimes the letters just disappear, sometimes it's replaced with 'e or e' because the clerk didn't know how to type é, sometimes the accent is just missing and becomes e, sometimes the clerk tries to be fancy and copy paste é in their system, but it only works locally and I then I'm named with �.
- French usually have a primary first name, 1 or 2 secondary first names, and a last name. In practice the additional first names are more or less used like American middle names, but legally speaking they are first names, there are no middle names in France. That means for most foreign countries where you can only have a single first name, it becomes the concatenation of all your first names. You are not "John" anymore, you are "John Bob Max", this is your first name from now on.
- Obviously concatenating first names creates stupidly long first names, so you will not really be "John Bob Max", but rather "John BM".
- I France when you have kids, you can decide for them to bear the father's name, the mother's name, or a concatenation of both. That concatenation can only be done with a space though, as hyphen-separated names are considered a single word. Most countries (e.g. Canada) have conflicting rules on this, meaning they will forcefully replace hyphens with spaces and vice versa.
- Overall clerks (in Europe especially) are not careful with inputting names in their systems. I would estimate 60% of the time, my name is spelled wrong (typo, character swap, localization, etc). This of course becomes ridiculous as countries are more and more trying to automate a lot of processes, but a single letter mismatch sends you to administrative hell.
My strategy of recent years, which seems to work, is to be *relentless* of having your name right every single time. Drop the accents and non latin1 letters systematically, don't accept any typo, imprecision or shortening, have your full first, middle and last names everywhere.
99% of the time the issues are because the operator/clerk don't want to bother, and think it won't be a huge deal. That's wrong, the snowball effect is real and painful. Once your name is wrong anywhere, it cascades in a nightmare quite quickly.