If you want to delete a SiteCollection in Office 365 in order to make a new SiteCollection with the exact same name, you should can experience a halt on all creations of SiteCollections. Even if the dialog box, asks if you want to delete the previous SiteCollection, the creation of a new one never happens. It just keeps waiting.
The only way to fix this, is to contact Microsoft Support, tell them to delete your broken SiteCollection completely and wait it out.
I suspect, that the PowerShell script, that is moving the SiteCollection from active, to deleted, isn’t finished, when you try to create a new one, with the same name. I have not yet had a chance to confirm this with the Office 35 support team.
Delete the SiteCollection, wait around 15-20 minutes for the PowerShell to finish and the Session to die. Then go and create your new SiteCollection and use the same name. If you can, just use another name all together.
I have filed Support Request with the Office 365 support team and will update my blog when I know more.
[[UPDATE: Oct. 1 2012: ]] I received this response from the Office 365 support team, confirming my suspicion]]
Regarding the number of occurrences you’ve experienced with this issue, it certainly is something we will see happening if site collections are quickly deleted and re-created. And, as you’d stated, it is to do with the server itself not completing the deletion process before a new site collection is created. A minimum of ten-fifteen minutes is advised when deleting and re-creating site collections this way, and in the case of the Team Site, 24-hours is recommended before creating a new top-level site collection.