Clear-SPListItems.ps1 simulates SPWeb.ProcessBatchData() using CSOM to batch ListItemCollection item deletes. Feedback welcome! To see what is going on under the covers, run Fiddler and watch the traffic for the requests.

Clear-SPListItems.ps1

# =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=
#       Script: Clear-SPListItems.ps1
#
#       Author: Pete Skelly
#		Twitter: ThreeWillLabs
#               http://www.threewill.com
#
#  Description: Purge list in Sharepoint Online - Office 365 using CSOM by 
#               batching CSOM calls to simulate SPWeb.ProcessBatchData().
#
#		WARNING: This script will DELETE all list items!!  Script provided
#               as is with no warranty.  Your mileage will vary.  Use this script
#               on a production list AT YOUR OWN RISK. 	    	
#
# =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=

param(
  [string]
  $siteUrl,
  
  [string]
  $userId,

  [string]
  $listName,

  [int]
  $batchSize
  
) 

$ErrorActionPreference  = 'Stop'

# ---------------------------------------------------------
# Load SharePoint 2013 CSOM  libraries.
Add-Type -Path "c:\Program Files\Common Files\microsoft shared\Web Server Extensions\15\ISAPI\Microsoft.SharePoint.Client.dll"
Add-Type -Path "c:\Program Files\Common Files\microsoft shared\Web Server Extensions\15\ISAPI\Microsoft.SharePoint.Client.Runtime.dll"
 


$password = Read-Host -Prompt "Enter password for $userId" -AsSecureString

$ctx = New-Object Microsoft.SharePoint.Client.ClientContext($siteUrl)
$credentials = New-Object Microsoft.SharePoint.Client.SharePointOnlineCredentials($userId, $password)
$ctx.Credentials = $credentials
 
$list = $ctx.get_web().get_lists().getByTitle($listName);
$ctx.Load($list)
$ctx.ExecuteQuery()
$itemCount = $list.ItemCount;
$listType =  $list.BaseType;
Write-Host "List contains $itemCount items.  List type of $listType"
	
#See http://msdn.microsoft.com/en-us/library/microsoft.sharepoint.client.camlquery(v=office.15).aspx for details on these calls
$itemsDeleted = 0;
$listID = $list.ID.ToString()

#create objects to be used to delete in batches
$camlQuery = New-Object Microsoft.SharePoint.Client.CamlQuery
#Create a query to get items by id's in batches
$camlQuery.ViewXml = "<View><ViewFields><FieldRef Name='Id'/></ViewFields><RowLimit>" + $batchSize + "</RowLimit></View>";		
$camlQuery.ListItemCollectionPosition = $null	#set initial query position (starts as null)
$items = $list.GetItems($camlQuery)		#execute the query
$ctx.Load($items);				#load the items 
$ctx.ExecuteQuery();				#execute the entire operation set
$retCount = $items.Count 
if ($retCount  -gt 0)
{
	do{
		Write-Verbose -Message "Query returned $itemCount items..."

		Write-Verbose -Message "Building batch..." 
		$items | 
			% {
				$delItem = $list.GetItemById($_.ID);
				$delItem.DeleteObject();
			}
		Write-Verbose -Message "Executing batch..." 
		$ctx.ExecuteQuery();
		
		$itemsDeleted = $itemsDeleted + $batchSize

	} while ($itemsDeleted -le $itemCount)	
}
else
{
	Write-Verbose -Message "No list items returned."
}

I got the same result as @jsiegmund above, but was able to resolve by replacing line 79 with the following lines (which I copied from before the do loop

$items = $list.GetItems($camlQuery)		#execute the query
$clientContext.Load($items);			#load the items
$clientContext.ExecuteQuery();			#execute the entire operation set