I had created a page (slug: vat-guides) and decided it needed children. So I deleted that page and attempted to create a folder called VAT Guides, with the slug vat-guides. It keeps telling me the URL already exists even though it blatantly doesn't. If I try to create a new page using that slug (vat-guides) it creates the page without problems, it's only if I try to create a folder with that slug. I've now deleted more than I'm happy to have. I've unpublished and republished numerous times and it hasn't helped.
Hopefully you can.