Hi Jerome Bollinger •,
Welcome to Microsoft Q&A forum.
As I understand, you are unable to create Azure Database for PostGreSQL Flexible server with the name of a deleted server.
And even after using dig you could see that server shows deleted.
I would recommend you to try Azure CLI/Powershell commands to check for DNS records in the relevant Private DNS Zone.
If found, try deleting and retry creating server if works fine.
Let us know how it goes.
Thanks