Error Fully qualified domain name and port overlaps with an application

In Entra admin center I created an Enterprise Application having an application segment:

Destination type: Fully qualified domain name

Destination: Host123.mycompany.com

Ports: 3389

Procotol: TCP and UDP

I DELETED that app.

I created a new Enterprise app.

I tried adding the same destination (fqdn, hostname, port, protocols)

When I try to save my new app I get an error message "Error: Fully qualified domain name and port overlaps with an application"

I went to App Registrations > Deleted applications and I found the old app there. I selected the checkbox and clicked 'Delete permanently'. The old app has been permanently deleted for more than 3 hours now. However each time I try to add this fully qualified domain name to my new app, I continue getting this error:

Error: Fully qualified domain name and port overlaps with an application

Network access settings

Application segment host and port already exists on application. conflictingApplication={"appId": <guid>, "objectId": <guid>, "appName": <guid>}