It's likely just taking longer that you expected.
From my experience, once a tenant is deleted it can be at least 2 or 3 months before things settle down.
Worst case, if you still have the tenant and subscription IDs you can contact Microsoft support and ask.
If you're being told they have nothing to do with Azure then it's likely the wrong support team.
Here's the typical link for finding support. But if you still have access to an Azure Portal login then the support link in the top right corner is recommended.