I contacted Twilio support and got the feedback, that my account is connected to region Ireland (ie1). So the Twilio Client Constructor has to look like this:

client = Client(
    account_sid=account_sid,
    username=api_key_sid,
    password=api_key_secret,
    edge="dublin",
    region="ie1",
)

So be aware of the credentials you use.