I started with the post from Nuno Mota with the same title to try to delete over 8000 nested folders from a user's mailbox.  They were all in Deleted Items and nested very very deeply.  Outlook no longer worked, nor did OWA and neither did MFCMAPI.  Unfortunately since I needed over 1000 folders to be deleted from a mailbox with over 10,000 folders Nuno's code didn't quite work for me.  

The attached EWS via PowerShell code shows how to page through large result sets and how to use the search filter to find the folder of interest.  Be warned that it is doing a hard delete, so depending on your circumstances you may want to make that a Soft Delete.  Also for my case of having to delete over 8000 folders, it did take almost two solid days to run...

Anyway I hope that someone else finds this useful and thanks to Nuno for providing the base code



# Script:    DeleteFoldersBottomUp.ps1 
# Purpose:    This scripts deletes every folder and subfolders for a specific top-folder starting from the last one 
# Author:    Twan van Beers (based on original script from Nuno Mota) 
# Date:        May2015 
[String] $mbxName = "someone@somewhere.com" 
[String] $topFolderName = "Deleted Items" 
[String] $dllPath = "C:\Program Files (x86)\Microsoft\Exchange\Web Services\2.1\Microsoft.Exchange.WebServices.dll" 
[Void] [Reflection.Assembly]::LoadFile($dllPath) 
$Service = New-Object Microsoft.Exchange.WebServices.Data.ExchangeService([Microsoft.Exchange.WebServices.Data.ExchangeVersion]::Exchange2010_SP1) 
$Service.AutodiscoverUrl($mbxName, {$True}) 
$RootFolderID = new-object Microsoft.Exchange.WebServices.Data.FolderId([Microsoft.Exchange.WebServices.Data.WellKnownFolderName]::Root, $mbxName$RootFolder = [Microsoft.Exchange.WebServices.Data.Folder]::Bind($Service$RootFolderID) 
$FolderView = New-Object Microsoft.Exchange.WebServices.Data.FolderView(1000) 
$FolderView.Traversal = [Microsoft.Exchange.WebServices.Data.FolderTraversal]::Deep 
# set up the search filter to look for the folder we want 
$SearchFilter = New-Object Microsoft.Exchange.WebServices.Data.SearchFilter+IsEqualTo( [Microsoft.Exchange.WebServices.Data.FolderSchema]::Displayname, $topFolderName ) 
$Response = $RootFolder.FindFolders($SearchFilter$FolderView) 
if$Response.folders.count -eq 1) { 
    $AllSubFolders = @() 
    # Found the folder, so start a new Deep search across all its sub-folders 
    $FolderView = New-Object Microsoft.Exchange.WebServices.Data.FolderView(1000) 
    $FolderView.Traversal = [Microsoft.Exchange.WebServices.Data.FolderTraversal]::Deep 
    $RootFolder = $Response.folders[0] 
    # get all of the subfolders by incrementing the Offset until nothing more to get     
    $MoreResults = $true 
        $Response = $RootFolder.FindFolders($FolderView) 
        $AllSubFolders +$Response.Folders 
        $MoreResults = $Response.MoreAvailable 
        $FolderView.Offset +$Response.Folders.count 
    } while$MoreResults -eq $true ) 
    # now we have all of the folders let's delete them from the bottom up 
    for$i = ($AllSubFolders.Count - 1); $i -gt 0; $i-- ) { 
        # sometimes it seems to time out (I had over 8000 folders to delete) if so then just retry the same one next time 
        if$error[0] -like '*the operation has timed out*' ) { $i++ }