Update
I described to an AI that the problem couldn't be with my email address or phone number because I received the verification codes.
The AI agreed.
That's why I ditched this email address and created a new one. Everything worked on the first try today. But I can't tell you if changing the email address was the solution or waiting another day. Apple's error messages are just not helpful.