With got the same issue with two tenants.
Even if you create a new public folder without mail-enabled (as admin) you can't delete it afterwards with outlook.
Deleting in EAC works tough.
PS: Just confirmed that it is an Outlook Bug
Using another Client like "emClient" lets you delete the public folders.