So we reported this issue to Microsoft who had to ask their engineering team to reset our vaults to deleted state which then allowed us to purge them finally.
They also said the following: "Delete and Purge operations don’t happen immediately; they usually take somewhere between 1-5m to complete, with a 2.5m rough average. Very occasionally, if you don't respect that and proceed to create > delete > purge in very quick succession, the key vault may get into a faulty state where our SLM jobs are not able to process the request immediately and the request becomes “stuck” and stays that way until released by engineering. That being said, this does happen very sporadically. To ensure that this doesn’t happen, an ideal workflow would be similar to the following: create KV > delete KV > wait 2.5m > purge KV."