Pushing to SQS through VPC Endpoint from lambda in private VPC fails

Hello!
I have setup a private VPC where some lambda functions reside. Now I would like one of the lambdas to send messages to a SQS queue. For that I have created a VPC Endpoint to SQS.
The policy for the VPC endpoint allows everything for every user.
The policy for the SQS queue allows all SQS operations on the queue from everywhere.
The policy on the lambda function allows all SQS operations.
The Security Group of the VPC Endpoint allows all traffic on all protocols.

Everything is on eu-central-1.
The lambda that I want to send a messate to SQS times out here at the send_message call:

def send_message():
sqs_client = boto3.client("sqs", region_name="eu-central-1")

_message = {"key": "value"}_  
_response = sqs_client.send_message(_  
    _QueueUrl="https://sqs.eu-central-1.amazonaws.com/<user-id>/<queue-name>",_  
    _MessageBody=json.dumps(message),_  
    _DelaySeconds=12_  
_)_  
_print ("Response: ", response)_  

(Of course I have substituted the user-id and queue-name with the actual ones).
I have also tried all the DNS addresses that VPC Endpoint provides, but none work.

What have I missed?