Hi @Tim Jin , welcome to Microsoft Q&A forum. Apologies for the trouble you are facing.
The commands provided by you worked perfectly fine when I tried. I created 2 azure PostgreSQL databases, then deleted one and restored new one with same name from other databases. Both are from same resource group.
it does not look a problem with "az postgres server restore" command.
As you mentioned this is occasional error, so I would suggest to retry the commands again and if you observe similar issue I can check with the internal team to look onto your subscription. Also I would suggest if you run the delete and restore commands with a little gap in time say 2-5 minutes to check if this issue is encountered then.
Please let me know.