To avoid data lost, Microsoft has introduced earlier in SharePoint Online the site collection recycle bin. This feature allows SharePoint Online administrators to restore deleted site collection.
This site collection recycle bin has also another impact which is blocking you when creating a new site collection which reuse an URL previously associated to a deleted site collection.
To continue the creation of the new site collection and so reuse the previous URL, the deleted site collection will have to be deleted from the recycle bin by hitting the check box Permanently delete the site collection from the recycle bin and continue.
This happen with both SharePoint Online 2010 and SharePoint Online 2013 until the deleted site collection has been automatically purged after 30 days
