An Azure backup service that provides built-in management at scale.
Your diagnosis is likely correct: ToBeDeleted is an intermediate service state, so the 14-day soft-delete retention period has not started.
If the storage account was deleted within the last 14 days, first try restoring the original account from Storage accounts > Restore. The original resource group must exist, the name must not have been reused, and recovery is best effort. If restoration succeeds, return to the vault, stop protection and delete backup data for each Azure file share, then go to Backup Infrastructure > Storage Accounts and unregister the account. For Azure Files, use the portal or Azure PowerShell; the Azure Backup CLI vault-deletion path supports VM backup items only.
If the account cannot be restored and the items remain in ToBeDeleted, repeated vault deletion or soft-delete commands will not remove the orphaned service references. The BMSUserErrorDisablingSoftDeleteStateNotAllowed response confirms that this now needs Microsoft-side cleanup. Q&A cannot initiate that escalation. Collect the vault/resource IDs, deleted account name, deletion time, job/correlation IDs and screenshots, then open a technical Azure Support request. With Basic support, you will need a paid support plan or an existing partner/enterprise support channel.